这题好像是初二时老师讲过的一道题，但是。。我没听？？反正没交过就对了。。
我本来想的是深搜+spfa，写到50+行实现不了？？果断看tj，floyd？？？（黑人问号？？？）这么简单的题绿了？？？
1 #include<set> 2 #include<map> 3 #include<list> 4 #include<queue> 5 #include<stack> 6 #include<string> 7 #include<cmath> 8 #include<ctime> 9 #include<vector> 10 #include<bitset> 11 #include<memory> 12 #include<utility> 13 #include<cstdio> 14 #include<sstream> 15 #include<iostream> 16 #include<cstdlib> 17 #include<cstring> 18 #include<algorithm> 19 using namespace std; 20 const int N=205; 21 const int oo=0x3f3f3f3f; 22 23 int n,k,m,s,t,z,y,zy; 24 int c[N],g[N][N],f[N][N]; 25 26 int main(){ 27 scanf("%d%d%d%d%d",&n,&k,&m,&s,&t); 28 memset(f,0x3f,sizeof(f)); 29 for(int i=1;i<=n;i++){ 30 scanf("%d",c+i);31 } 32 for(int i=1;i<=k;i++){ 33 for(int j=1;j<=k;j++){ 34 scanf("%d",g[i]+j); 35 } 36 } 37 for(int i=1;i<=m;i++){ 38 scanf("%d%d%d",&z,&y,&zy); 39 if(!g[c[y]][c[z]]&&c[y]!=c[z]){ 40 f[z][y]=min(f[z][y],zy); 41 } 42 if(!g[c[z]][c[y]]&&c[y]!=c[z]){ 43 f[y][z]=min(f[y][z],zy); 44 } 45 } 46 if(c[s]==c[t]){ 47 printf("-1 "); 48 return 0; 49 } 50 for(int i=1;i<=n;i++){ 51 for(int j=1;j<=n;j++){ 52 if(i!=j){ 53 for(int k=1;k<=n;k++){ 54 if(j!=k&&i!=k){ 55 if(f[i][k]+f[k][j]<f[i][j]){ 56 f[i][j]=f[i][k]+f[k][j]; 57 } 58 } 59 } 60 } 61 } 62 } 63 if(f[s][t]==oo){ 64 printf("-1 "); 65 } 66 else{ 67 printf("%d ",f[s][t]); 68 } 69 return 0; 70 }
好吧其实从代码长度上可能值了绿题的程度？？但反正想起来。。。哦我第一次想的是spfa。。。嗯那这题确实是绿题！！有过之而无不及！！！