解答者,蒟蒻将送上关注
本地CE,实在看不出来 另外请大佬帮我看看代码逻辑有无问题,堆优化掌握的不太扎实,谢谢。
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;
int n, m, s, t, dis[200], s1, s2, s3;
bool vis[200];
struct Y {
int t1, t2;//t1为点,t2为距离
};
vector<Y> v[200];//v[u]是和点u联通的所有点的集合;
priority_queue<Y, vector<Y>, greater<Y>> q;////优先队列(小根堆),意义同上
void dijkstra() {
for(int i = 1; i <= n; i++) {
dis[i] = INF;
}
dis[s] = 0;//dis为最短距离
q.push({s, 0});
while(!q.empty()) {
t = q.top().t1;
q.pop();
if(vis[t]) continue;//如果已经查过了,就跳过
vis[t] = true;//标记是否查过
for(auto i : v[t]) {//遍历所有能到达点t的点
if(dis[i.t1] > dis[t] + i.t2) {
//i.t1为点的编号
//i.t2表示点i到t的距离
dis[i.t1] = dis[t] + i.t2;
q.push({i.t1, dis[i.t1]});
}
}
}
}
int main() {
scanf("%d %d %d", &n, &m, &s);
for(int i = 1; i <= m; i++) {
scanf("%d %d %d", &s1, &s2, &s3);
v[s1].push_back({s2, s3});//建双向边
v[s2].push_back({s1, s3});
}
dijkstra();
for(int i = 1; i <= n; i++) {
printf("%d ",dis[i]);
}
return 0;
}