給定一個(gè)圖，（V 3*10^4， E 1.5*10^5）,如此大規(guī)模的圖，求一個(gè)最短路，只能使用SPFA（使用棧進(jìn)行優(yōu)化）
1: #include <queue>
2: #include <iostream>
3: #include <string.h>
4: #include <stdio.h>
5: using namespace std;
6: #define MAXN 30010 // vertex
7: #define MAXM 150010 // edge
8: #define INF 0x3F3F3F3F
9:
10: struct node
11: {
12: int v, w, next;
13: }pnt[MAXM];
14:
15: int head[MAXN];
16: int dis[MAXN];
17: bool vis[MAXN];
18: int cnt[MAXN]; // the number of the operation of push to Quque. negatvie cycle.
19: int num = 0; // the index of the edge
20: int N ; // the number of the vertex.
21: int M ; // the number of edges
22: int src, sink;
23: void addedge(int u, int v, int w)
24: {
25: pnt[num].v = v; pnt[num].w= w;
26: pnt[num].next = head[u]; head[u] = num++;
27: }
28:
29: int SPFA()
30: {
31: for(int i=0; i<=N; i++)
32: {
33: vis[i]=0; dis[i] = INF; cnt[i] = 0;
34: }
35:
36: int Q[MAXM], top=1;
37: Q[0] = src; vis[src] = 1;
38: dis[src] = 0;
39: while(top)
40: {
41: int u = Q[--top]; vis[u] = 0;
42: for(int i = head[u]; i!=-1; i=pnt[i].next)
43: {
44: int v = pnt[i].v;
45: if(dis[v]> dis[u] + pnt[i].w )
46: {
47: dis[v]= dis[u] +pnt[i].w;
48: if(!vis[v])
49: {
50: Q[top++] = v; vis[v]= 1;
51: }
52: }
53:
54: }
55: }
56:
57:
58:
59: return dis[sink];
60: }
61:
62: int main()
63: {
64: //freopen("3159.txt", "r", stdin);
65: while(scanf("%d%d", &N , &M)!= EOF)
66: {
67: num = 0;
68: memset(head, -1, sizeof(head));
69: for(int i=0; i<M; i++)
70: {
71: int a, b, c;
72: scanf("%d%d%d", &a, &b, &c);
73: addedge(a, b,c);
74: }
75: //cout<<num<<endl;
76: src = 1; sink = N;
77: //cout<<"src "<<src<<" sink "<<N<<endl;
78: printf("%d\n", SPFA());
79: }
80: return 0;
81: }