http://acm.hust.edu.cn/thx/problem.php?id=1163
今天做了一个题，郁闷了一下午，vector又忘记clear了，~~~5555，是一个dij，求最短路的最大距离，我用vector模拟了一个邻接表，因为v的数目达到了10000，矩阵是不行的。但却每每在最后忘了clear，多case啊。。。。
不过dij的速度慢的很，以后注意，教训！
1
/**//****************************************************************
2
Problem: 1163
3 User: Torres
4 Language: C++
5 Result: Accepted
6 Time:1448 ms
7 Memory:1480 kb
8
****************************************************************/
9
10#include<iostream>
11#include<vector>
12#include<algorithm>
13using namespace std;
14#define Nmax 10005
15const int oo=0x7fffffff;
16template<class T>void print(T *a,int n)
{for(int i=0;i<n;i++)cout<<a[i]<<" ";cout<<endl;}
17
18typedef struct node{
19 int end,value;
20
node(int a=0,int b=oo){
21 end=a;
22 value=b;
23
}
24}node;
25
26vector<node> dist[Nmax];
27int closed[Nmax];
28bool used[Nmax];
29
30int main()
31{
32 int T,ca,P,C,x,y,dis1,dis2;
33 int i,j,k;
34 node temp;
35 int m,re;
36 scanf("%d",&T);
37 for(ca=1;ca<=T;ca++){
38 scanf("%d%d",&P,&C);
39 for(i=0;i<P;i++)
40 scanf("%d",&closed[i]);
41 for(i=1;i<=C;i++){
42 scanf("%d%d%d%d",&x,&y,&dis1,&dis2);
43 temp.end=y;
44 temp.value=dis1;
45 dist[x].push_back(temp);
46 temp.end=x;
47 temp.value=dis2;
48 dist[y].push_back(temp);
49 }
50 memset(used,false,sizeof(used));
51 for(i=1;i<P;i++){
52 int min=oo;
53 int itemp;
54 for(k=0;k<P;k++)
55 if(!used[k]&&closed[k]<min){
56 min=closed[k];
57 itemp=k;
58 }
59 used[itemp]=true;
60 int sz=dist[itemp].size();
61 for(k=0;k<sz;k++){
62 j=dist[itemp][k].end;
63 int v=dist[itemp][k].value;
64 if(!used[j]&&closed[j]>closed[itemp]+v)
65 closed[j]=closed[itemp]+v;
66 }
67 }
68 m=closed[0];re=0;
69 for(i=0;i<P;i++)
70 if(closed[i]>m){
71 m=closed[i];
72 re=i;
73 }
74 printf("Scenario #%d:\n%d\n\n",ca,re);
75 for(i=0;i<Nmax;i++) dist[i].clear();
76 }
77 return 0;
78}
79