fuzhu_2011_09_03 @ 2024-08-31 19:51:19
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const long long inf = (1ll << 63) - 1;
int n,m,s;
int vis[maxn];//判断这个节点是否被遍历过
long long dis[maxn];//i节点到s目前的最短路
struct node{
long long to,w;
friend bool operator < (node a,node b) {
return a.w < b.w;
}//重载运算符维护一个小根堆
};
priority_queue<node> q;
struct edge{
long long to,w;
};
vector <edge> g[maxn];
int main() {
//cout << inf << endl;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u,v,w;
cin >> u >> v >> w;
g[u].push_back(edge{v,w});
g[v].push_back(edge{u,w});
}
for (int i = 1; i <= n; i++)
dis[i] = inf;
dis[s] = 0;
q.push(node{s,0});
while (!q.empty()) {
node now = q.top();
q.pop();
int v = now.to;
if (vis[v]) continue;
vis[v] = 1;
for (int i = 0; i < g[v].size(); i++) {
long long t = g[v][i].to;
if (dis[t] > (long long)(dis[v] + g[v][i].w)) {
dis[t] = dis[v] + g[v][i].w;
q.push(node{t,dis[t]});
}
}
}
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
return 0;
}
by xd22fuzhu @ 2024-08-31 19:57:57
不是哥么,这是有向图
by SBBSBSBSBSB @ 2024-08-31 20:02:00
方向让你吃了,把单车道变成了双车道
by yandi_ @ 2024-09-07 20:19:35
g[u].push_back(edge{v,w});
g[v].push_back(edge{u,w});
有向边:我啥时候变无向边了?