Botter @ 2024-04-12 19:44:02
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#define inf 0x3f3f3f
//#define int long long
using namespace std;
struct node{
long v,w;
};
vector<node>e[2*100005+5];
long d[2*100005+5];
bool vis[2*100005+5];
long e_,v,w,s,n,m;
priority_queue<pair<long,long>>q;
void dij(long s){
for (long i = 0 ; i<= n ; i++) {
d[i] = inf;
}
d[s] = 0;
q.push({0,s});
while(q.size()){
auto t = q.top() ; q.pop();
long u = t.second;
if (vis[u]) continue;
vis[u] = 1;
for (node ed : e[u]){
long v = ed.v , w = ed.w;
if (d[v] > d[u]+w){
d[v] = d[u]+w;
q.push({-d[v],v});
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> s;
for (long i = 1 ; i <= m ; i++){
cin >> e_ >> v >> w;
e[e_].push_back({v,w});
}
dij(s);
for (long i = 1 ; i <= n ; i++){
cout << d[i] << " ";
}
return 0;
}
by Botter @ 2024-04-12 19:48:03
开了long long还是wa了
by chengcheng567 @ 2024-04-12 19:48:45
不是,哥们,你inf开小了
by chengcheng567 @ 2024-04-12 19:49:56
把inf开成2e9
by chengcheng567 @ 2024-04-12 19:50:26
这题有保证sigma w<=1e9所以不用long long
by chengcheng567 @ 2024-04-12 19:51:25
你现在的inf是4144959只有4e6左右
by Botter @ 2024-04-13 23:19:58
@chengcheng567 A了,谢谢大佬