单源最短路
差点被memset害了
#include<bits/stdc++.h>
#define ll long long
const ll N = 1e5 + 100;
ll n,m,s;
ll e[N],ne[N],idx,h[N],w[N];
std::queue<ll> op;
ll cnt[N];//统计每个点的最短路用的最少路程
ll dis_ll[N];//记录每个点的最短路的值
bool ok[N];
void add(ll a,ll b,ll c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
ll dis(){
// std::memset(dis_ll,0x3f,sizeof dis_ll);
for(ll i = 1; i <= n; i ++){
dis_ll[i] = 1e11;
}
// std::cout << "这时候的初始值:" << dis_ll[1] << "\n";
dis_ll[s] = 0;
ok[s] = true;
while(op.size()){
ll now_point = op.front();
op.pop();
ok[now_point] = false;
for(ll i = h[now_point]; i != -1; i = ne[i]){
ll num = e[i];
if(dis_ll[num] > dis_ll[now_point] + w[i]){
dis_ll[num] = dis_ll[now_point] + w[i];
cnt[num] = cnt[now_point] + 1;
if(cnt[num] > n) return -1;
if(ok[num] == false){
op.push(num);
ok[num] = true;
}
}
}
}
return 1;
}
void solve(){
std::memset(cnt,0,sizeof cnt);
std::memset(h,-1,sizeof h);
std::cin >> n >> m >> s;
for(ll i = 1; i <= m; i ++){
ll a,b,c;
std::cin >> a >> b >> c;
add(a,b,c);
}
//先找是否存在负环
for(ll i = 1; i <= n; i ++){
op.push(i);
}
ll res = dis();
if(res == -1){
std::cout << -1 << '\n';
}
else{//没有负环的产生
op.push(s);
ll uu = dis();
for(ll i = 1; i <= n; i ++){
if(dis_ll[i] >= 1e6) std::cout << "NoPath\n";
else std::cout << dis_ll[i] << '\n';
}
}
// std::cout << 0x3f3f3f3f << "\n";
return ;
}
signed main() {
std::ios::sync_with_stdio(false); std::cin.tie(0);std::cout.tie(0);
int t = 1;
while(t --)
solve();
return 0;
}