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;
}
© 2015 HUST ACMICPC TEAM. All Right Reserved.