九度教程第79題

C語言源碼： [cpp]   #include<stdio.h>   #include<limits.h>   #define maxsize 610   int E[maxsize][maxsize];   int T[maxsize][2];   int ed[10009][3];   int main()   {       int n,m,a[maxsize],i,j,fmin,min,sum,p,q;       scanf("%d",&n);       while(n)       {           for(i=0;i<n;i++)               for(j=0;j<n;j++)                   E[i][j]=INT_MAX;           scanf("%d",&m);           i=1;           while(i<=m)           {               scanf("%d %d %d",&ed[i][0],&ed[i][1],&ed[i][2]);               i++;           }           for(i=0;i<n;i++)               scanf("%d",&a[i]);           i=1;           while(i<=m)           {               p=ed[i][0]-1;               q=ed[i][1]-1;               if(a[p]==1&&a[q]==2)                   E[p][q]=ed[i][2];               else                   if(a[p]==2&&a[q]==1)                       E[q][p]=ed[i][2];                   else                   {                       E[p][q]=ed[i][2];                       E[q][p]=ed[i][2];                   }                   i++;           }           for(i=0;i<n;i++)           {               T[i][0]=0;               T[i][1]=INT_MAX;           }           i=0;           sum=0;           T[0][0]=1;           T[0][1]=0;           while(i!=1)           {               for(j=0;j<n;j++)               {                   if(T[j][0]==0&&E[i][j]!=INT_MAX&&sum+E[i][j]<T[j][1])                       T[j][1]=sum+E[i][j];               }               fmin=-1;               min=INT_MAX;               for(j=0;j<n;j++)               {                   if(T[j][0]==0&&T[j][1]<min)                   {                       fmin=j;                       min=T[j][1];                   }               }               sum=min;               if(fmin==-1)                   break;               else                   i=fmin;               T[i][0]=1;           }           if(T[1][1]!=INT_MAX)               printf("%d\n",T[1][1]);           else               printf("-1\n");           scanf("%d",&n);       }   }