poj 1797 dij变形

1. #include<iostream>
2. usingnamespacestd;
4. inttable[1001][1001]={0};
5. intd[1001];
6. voiddij(intN);
8. intmain()
9. {
11. freopen("in.txt","r",stdin);
12. intT,N,M,i,a,b,c,t(1);
13. cin>>T;
14. while(T--)
15. {
16. scanf("%d%d",&N,&M);
18. for(i=0;i<M;i++)
19. {
21. scanf("%d%d%d",&a,&b,&c);
22. table[a-1][b-1]=c;
23. table[b-1][a-1]=c;
26. }
27. dij(N);
28. printf("Scenario#%d:\n",t++);
30. printf("%d\n\n",d[N-1]);
32. memset(table,0,sizeof(table));
33. memset(d,0,sizeof(d));
37. }
41. return0;
42. }
44. voiddij(intN)
45. {
46. intv(0),max(0),i,j,w;
47. shortf[1001]={0};
48. for(i=0;i<N;i++)
49. d[i]=table[v][i];
50. f[v]=1;
51. d[v]=0;
52. for(i=1;i<N;i++)
53. {
55. max=0;
56. for(j=1;j<N;j++)
57. if(!f[j]&&d[j]>max)
58. {max=d[j];v=j;}
59. f[v]=1;
60. for(w=1;w<N;w++)
61. if(!f[w])
62. {
63. if(table[v][w]>max)
64. d[w]=max;
65. if(table[v][w]<=max)
66. if(table[v][w]>d[w])
67. d[w]=table[v][w];
68. }
69. }
76. }