膜膜膜

膜膜膜

膜膜膜

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
long long dis[1010];
struct node{
int u,v;
long long w;
}e[100100];
int main(){
long long INF=(long long)pow(10,18);
int n,m,s,i;
scanf("%d%d%d",&n,&m,&s);
for(i=1;i<=m;i++)
scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
for(i=1;i<=n;i++)dis[i]=INF;
dis[s]=0;
int k;
for(k=1;k<n;k++)
for(i=1;i<=m;i++)
if(dis[e[i].v]>dis[e[i].u]+e[i].w)
dis[e[i].v]=dis[e[i].u]+e[i].w;
int flag=0;
for(i=1;i<=m;i++)
if(dis[e[i].v]>dis[e[i].u]+e[i].w){
flag=1;
break;
}
if(flag==1)puts("-1");
else for(i=1;i<=n;i++){
if(dis[i]==INF)puts("NoPath");
else printf("%lld\n",dis[i]);
}
}
代码放在这里