社区讨论
是因为用了STL才会T吗?????
P4779【模板】单源最短路径(标准版)参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo83uxd6
- 此快照首次捕获于
- 2023/10/27 12:20 2 年前
- 此快照最后确认于
- 2023/10/27 12:20 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,s,u,v,w;
int dis[100100];
bool blue[100100];
vector<int> to[100100], val[100100];
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >q;
inline void read(int &a){
int x = 0, f = 1;
char c = getchar();
while(c<'0' || c>'9'){
if(c == '-') f = -f;
c = getchar();
}
while(c>='0' && c<='9'){
x = (x<<3) + (x<<1) + (c-'0');
c = getchar();
}
a = x*f;
}
inline void write(int x){
if(x >= 10) write(x/10);
putchar(x%10 + '0');
}
int main(){
read(n), read(m), read(s);
for(int i = 1; i <= m; i++){
read(u), read(v), read(w);
to[u].push_back(v);
val[u].push_back(w);
}
memset(dis, 127/3, sizeof(dis));
for(int i = 1; i <= n; i++) blue[i] = true;
dis[s] = 0;
q.push(make_pair(0,s));
for(int i = 1; i <= n; i++){
int now = q.top().second;
q.pop();
while(blue[now] == false && !q.empty()){
now = q.top().second;
q.pop();
}
blue[now] = false;
for(int j = 0; j < to[now].size(); j++){
int end = to[now][j];
int len = val[now][j];
if(dis[now] + len < dis[end]){
dis[end] = dis[now] + len;
q.push(make_pair(dis[end], end));
}
}
}
for(int i = 1; i <= n; i++){
write(dis[i]);
putchar(' ');
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...