九度教程第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);
}
}
补充：软件开发 , C++ ,
