http://acm.pku.cn/JudgeOnline/problem?id=3159求最短路Dij,数据太强了
1![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//********************************
2
Source Code
3![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
4
Problem: 3159 User: Torres
5
Memory: 3328K Time: 1422MS
6
Language: C++ Result: Accepted
7
********************************/
8
#include<iostream>
9
#include<vector>
10
#include<algorithm>
11
#include<queue>
12
using namespace std;
13![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
14
const int Nmax=30005;
15
const int oo=0x7fffffff;
16![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
typedef struct node
{
18
int end,len;
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
node(int a=0,int b=oo):end(a),len(b)
{};
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool operator<(const node &a)const
{
21
return this->len>a.len;
22
}
23
}node;
24![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
25
vector<vector<node> >dist(Nmax);
26
bool used[Nmax];
27
int N,M,i,j;
28![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
29
int Dijkstra(int s,int e)
30![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
31
vector<int>closed(N+1,oo);
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool used[Nmax]=
{false};
33
priority_queue<node>q;
34
q.push(node(s,0));
35
closed[s]=0;
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(!q.empty())
{
37
node ntemp=q.top();
38
q.pop();
39
if(used[ntemp.end])continue;
40
if(ntemp.end==e)return ntemp.len;
41
used[ntemp.end]=true;
42![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
43
int sz=dist[ntemp.end].size();
44![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=0;j<sz;j++)
{
45
int en=dist[ntemp.end][j].end;
46
int le=ntemp.len+dist[ntemp.end][j].len;
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!used[en]&&le<closed[en])
{
48
closed[en]=le;
49
q.push(node(en,le));
50
}
51
}
52
53
}
54
return closed[e];
55
}
56![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
57
int main()
58![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
59
int s,e,l;
60
scanf("%d%d",&N,&M);
61![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=1;i<=M;i++)
{
62
scanf("%d%d%d",&s,&e,&l);
63
dist[s].push_back(node(e,l));
64
}
65
printf("%d\n",Dijkstra(1,N));
66
return 0;
67
}
68![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
69![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
以后用vector定义二维数组用vector<vector<> >v吧,不要vector<>v[]。