題面

這題好像是初二時(shí)老師講過(guò)的一道題，但是。。我沒(méi)聽(tīng)？？反正沒(méi)交過(guò)就對(duì)了。。

我本來(lái)想的是深搜+spfa，寫(xiě)到50+行實(shí)現(xiàn)不了？？果斷看tj，floyd？？？（黑人問(wèn)號(hào)？？？）這么簡(jiǎn)單的題綠了？？？

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\n"); 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\n"); 65 } 66 else{ 67 printf("%d\n",f[s][t]); 68 } 69 return 0; 70 }

好吧其實(shí)從代碼長(zhǎng)度上可能值了綠題的程度？？但反正想起來(lái)。。。哦我第一次想的是spfa。。。嗯那這題確實(shí)是綠題！！有過(guò)之而無(wú)不及！！！

轉(zhuǎn)載于:https://www.cnblogs.com/hahaha2124652975/p/11150202.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的P1078 文化之旅的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。