http://acm.pku.cn/JudgeOnline/problem?id=3159求最短路Dij，數據太強了
1
/**//********************************
2
Source Code
3
4Problem: 3159 User: Torres
5Memory: 3328K Time: 1422MS
6Language: C++ Result: Accepted
7
********************************/
8
#include<iostream>
9#include<vector>
10#include<algorithm>
11#include<queue>
12using namespace std;
13
14const int Nmax=30005;
15const int oo=0x7fffffff;
16
17typedef struct node
{
18 int end,len;
19
node(int a=0,int b=oo):end(a),len(b){};
20 bool operator<(const node &a)const{
21 return this->len>a.len;
22
}
23}node;
24
25vector<vector<node> >dist(Nmax);
26bool used[Nmax];
27int N,M,i,j;
28
29int Dijkstra(int s,int e)
30{
31 vector<int>closed(N+1,oo);
32 bool used[Nmax]={false};
33 priority_queue<node>q;
34 q.push(node(s,0));
35 closed[s]=0;
36 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
43 int sz=dist[ntemp.end].size();
44 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 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
57int main()
58{
59 int s,e,l;
60 scanf("%d%d",&N,&M);
61 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
69
以后用vector定義二維數組用vector<vector<> >v吧,不要vector<>v[]。