http://acm.hust.edu.cn/thx/problem.php?id=1163
今天做了一个题,郁闷了一下午,vector又忘记clear了,~~~5555,是一个dij,求最短路的最大距离,我用vector模拟了一个邻接表,因为v的数目达到了10000,矩阵是不行的。但却每每在最后忘了clear,多case啊。。。。
不过dij的速度慢的很,以后注意,教训!
1![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//****************************************************************
2
Problem: 1163
3
User: Torres
4
Language: C++
5
Result: Accepted
6
Time:1448 ms
7
Memory:1480 kb
8
****************************************************************/
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10
#include<iostream>
11
#include<vector>
12
#include<algorithm>
13
using namespace std;
14
#define Nmax 10005
15
const int oo=0x7fffffff;
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
template<class T>void print(T *a,int n)
{for(int i=0;i<n;i++)cout<<a[i]<<" ";cout<<endl;}
17![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
typedef struct node
{
19
int end,value;
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
node(int a=0,int b=oo)
{
21
end=a;
22
value=b;
23
}
24
}node;
25![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
26
vector<node> dist[Nmax];
27
int closed[Nmax];
28
bool used[Nmax];
29![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
30
int main()
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1;i<P;i++)
{
52
int min=oo;
53
int itemp;
54
for(k=0;k<P;k++)
55![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)