鏈接：最短路

A.HDU 2544? ??最短路

算是最基礎的題目了吧.............我采用的是Dijkstra算法.......

代碼：

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 #define inf 0x3f3f3f3f 7 int map[105][105],d[105],vis[105],n,m; 8 9 int Dijkstra() 10 { 11 memset(vis,0,sizeof(vis)); 12 for(int i=0;i<=n;i++) 13 d[i]=(i==1?0:inf); 14 for(int i=1;i<=n;i++) 15 { 16 int x,minn=inf; 17 for(int j=1;j<=n;j++) 18 if(!vis[j] && d[j]<minn) 19 { 20 minn=d[j]; 21 x=j; 22 } 23 vis[x]=1; 24 for(int y=1;y<=n;y++) 25 d[y]=min(d[y],map[x][y]+d[x]); 26 } 27 return d[n]; 28 } 29 30 int main() 31 { 32 int i,u,v,w; 33 while(~scanf("%d%d",&n,&m),n,m) 34 { 35 memset(map,inf,sizeof(map)); 36 for(i=0;i<m;i++) 37 { 38 scanf("%d%d%d",&u,&v,&w); 39 map[u][v]=map[v][u]=w; 40 } 41 printf("%d\n",Dijkstra()); 42 } 43 return 0; 44 }

B.HDU 3790??最短路徑問題

......Loading......

C.HDU 3665? ?Seaside

題意：就是找到海邊的最短路~

這道題其實還是很簡單的~就是輸入麻煩的點.......╮(╯▽╰)╭把輸入搞清了就SO EASY~

代碼：

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int inf=100000000; 7 int a[205][205],b[205]; 8 9 int main() 10 { 11 int u,v,i,j,n,s,t,k,sum,ll,number,maxx; 12 while(~scanf("%d",&n)) 13 { 14 for(i=0;i<n;i++) 15 for(j=0;j<n;j++) 16 a[i][j]=inf; 17 for(i=0;i<n;i++) 18 a[i][i]=0; 19 for(i=0;i<n;i++) 20 { 21 scanf("%d%d",&u,&b[i]); //u代表該鎮與幾個town相連，b[i]代表該鎮是否臨海~ 22 for(j=0;j<u;j++) 23 { 24 scanf("%d%d",&number,&ll); //number代表是哪個鎮，ll代表u鎮與該鎮相連的距離 25 if(a[i][number]>ll) 26 a[i][number]=a[number][i]=ll; 27 } 28 } 29 for(i=0;i<n;i++) 30 for(j=0;j<n;j++) 31 for(k=j+1;k<n;k++) 32 if(a[j][k]>a[j][i]+a[i][k]) 33 { 34 a[j][k]=a[j][i]+a[i][k]; 35 a[k][j]=a[j][k]; 36 } 37 maxx=inf; 38 for(i=0;i<n;i++) 39 { 40 if(a[0][i]<maxx && b[i]==1) 41 maxx=a[0][i]; 42 } 43 printf("%d\n",maxx); 44 } 45 return 0; 46 }

//memory：264KB ? time：0ms

D.HDU 1869? ?六度分離

簡而言之~是很簡單的題~把每個人的關系都弄出來~只要都滿足不大于6個人就是YES，反之NO~

代碼：

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int inf=100000000; 7 int a[205][205]; 8 9 int main() 10 { 11 int u,v,w,i,j,n,m,s,t,k; 12 while(~scanf("%d%d",&n,&m)) 13 { 14 for(i=0;i<n;i++) 15 for(j=0;j<n;j++) 16 a[i][j]=inf; 17 for(i=0;i<n;i++) 18 a[i][i]=0; 19 for(i=0;i<m;i++) 20 { 21 scanf("%d%d",&u,&v); 22 a[u][v]=a[v][u]=1; 23 } 24 for(i=0;i<n;i++) 25 for(j=0;j<n;j++) 26 for(k=j+1;k<n;k++) 27 if(a[j][k]>a[j][i]+a[i][k]) 28 { 29 a[j][k]=a[j][i]+a[i][k]; 30 a[k][j]=a[j][k]; 31 } 32 w=0; 33 for(i=0;i<n;i++) 34 for(j=i;j<n;j++) 35 if(a[i][j]>7) 36 {w=-1; break;} 37 if(w==-1) printf("No\n"); 38 else 39 printf("Yes\n"); 40 } 41 return 0; 42 }

//memory：320KB ? time：31ms

E.HDU 1874? ?暢通工程續

是很簡單的題~和A極端的像.............但TLE很多次........剛開始百思不得其解........結果后來發現，就是與A題太像了，結果自己就擅自做主把A題的“輸入0,0退出”，直接就套到這道題上了.........T T.........讓人淚奔的錯誤啊.......

代碼：

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int inf=100000000; 7 int a[205][205]; 8 9 int main() 10 { 11 int u,v,w,i,j,n,m,s,t,k; 12 while(~scanf("%d%d",&n,&m)) 13 { 14 for(i=0;i<n;i++) 15 for(j=0;j<n;j++) 16 a[i][j]=inf; 17 for(i=0;i<n;i++) 18 a[i][i]=0; 19 for(i=0;i<m;i++) 20 { 21 scanf("%d%d%d",&u,&v,&w); 22 if(a[u][v]>w) 23 a[u][v]=a[v][u]=w; 24 } 25 for(i=0;i<n;i++) 26 for(j=0;j<n;j++) 27 for(k=j+1;k<n;k++) 28 if(a[j][k]>a[j][i]+a[i][k]) 29 { 30 a[j][k]=a[j][i]+a[i][k]; 31 a[k][j]=a[j][k]; 32 } 33 scanf("%d%d",&s,&t); 34 if(a[s][t]==inf) printf("-1\n"); 35 else 36 printf("%d\n",a[s][t]); 37 } 38 return 0; 39 }

//memory：332KB ? time：31ms

F.HDU 1317? ?XYZZY

......Loading......

G.HDU 4360? ? ?As long as Binbin loves Sangsang

......Loading......

H.POJ 1847? ??Tram

......Loading......

I.POJ 1062? ? ?昂貴的聘禮

......Loading......

轉載于:https://www.cnblogs.com/teilawll/p/3254226.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的8-12-COMPETITION的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。