Floyd算法
#include<iostream> #include<string.h> using namespace std; #define INF 1000000 int edge[120][120]; int A[120][120]; int a[123]; int dis[123]; int n,m; int sum; void Floyd() { int k,i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(edge[i][j]&&a[j]<0) A[i][j]=a[j]; else if(edge[i][j]&&a[j]>0) A[i][j]=a[j]*(-1); else A[i][j]=0; } for(k=1;k<=n;k++) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(k==i||k==j) continue; if(A[i][k]!=0&&A[k][j]!=0&&A[i][k]+A[k][j]<A[i][j]) A[i][j]=A[i][k]+A[k][j]; } } int max; max=A[1][sum]*(-1); if(max==a[sum]*(-1)&&edge[1][sum]) cout<<max<<endl; else if(max==a[sum]*(-1)&&edge[1][sum]!=1) cout<<\"What is a fucking day!\"<<endl; else if(max>a[sum]*(-1)) cout<<max<<endl; else cout<<\"What is a fucking day!\"<<endl; } int main() { int i,j; int u,v; int min; int flag; cin>>n>>m; memset(edge,0,sizeof(edge)); for(i=1;i<=m;i++) { cin>>u>>v; edge[u][v]=1; } min=0; flag=0; for(i=2;i<=n;i++) { cin>>a[i]; if(a[i]<0) flag=1; if(min>a[i]){ min=a[i]; sum=i; } } // memset(visit,0,sizeof(visit)); for(i=1;i<=n;i++) { if(a[i]<0) { for(j=1;j<=n;j++) { if(edge[i][j]) edge[i][j]=0; } } } if(!flag) cout<<\"What is a fucking day!\"<<endl; else Floyd(); return 0; }