话说好久没写上来了。
今天比较高兴，她竟然去了我的QZone！！！
虽然一点准备都没有，（我都是今天才知道的），但是好高兴。。
PKU3268
可以写SPFA，可以写DijkstraWithHeap，反正别傻傻的做n次就行。。
PKU3268
1/**//*
2
Task: pku3268
3Author: DMKaplony
4Date: 3/15/2010 6:59 PM CST
5State:
6 6573720 DMKaplony 3268 Accepted 372K 47MS C++ 2675B 2010-03-15 19:24:18
7 6573719 DMKaplony 3268 Compile Error G++ 2675B 2010-03-15 19:24:08
8Memo: DijkstraWithHeap|SPFA(v)--Forxcc0322
9
*/
10
11#include <iostream>
12
13#define gmax(a,b) ((a)>(b)?(a):(b))
14#define INF 0x7FFFFFFF
15#define MAXE 500000
16#define MAXV 5000
17
18using namespace std;
19
20struct ENode
{
21 int ver;
22 int w;
23 ENode *next;
24
void SetData(int V, int W, ENode *N){
25 ver = V;
26 w = W;
27 next = N;
28
}
29 };
30
31ENode cnode[MAXE];
32int noder = 0;
33ENode *net[MAXV], *revnet[MAXV];
34bool inQ[MAXV];
35int Q[MAXV];
36int dis[MAXV], revdis[MAXV];
37int n, m, x;
38
39
40void AddEdge(int u, int v, int w){
41 cnode[++noder].SetData(v, w, net[u]);
42 net[u] = &cnode[noder];
43 cnode[++noder].SetData(u, w, revnet[v]);
44 revnet[v] = &cnode[noder];
45 }
46
47void Spfa(){
48 int i;
49 int head = 0;
50 int tail = 0;
51 for (i=1; i<n+1; i++){
52 dis[i] = INF >> 1;
53 }
54 dis[x] = 0;
55 Q[++tail] = x;
56 memset(inQ, 0, sizeof(inQ));
57 inQ[x] = 1;
58 while (head != tail){
59 if (++head == MAXV)
60 head = 0;
61 int u = Q[head];
62 inQ[u] = 0;
63 for (ENode *e=net[u]; e; e=e->next){
64 if (dis[e->ver] > dis[u] + e->w){
65 dis[e->ver] = dis[u] + e->w;
66 if (!inQ[e->ver]){
67 if (++tail == MAXV)
68 tail = 0;
69 Q[tail] = e->ver;
70 inQ[e->ver] = 1;
71 }
72 }
73 }
74 }
75
76
77
78 head = tail = 0;
79 for (i=1; i<n+1; i++){
80 revdis[i] = INF >> 1;
81 }
82 revdis[x] = 0;
83 Q[++tail] = x;
84 memset(inQ, 0, sizeof(inQ));
85 inQ[x] = 1;
86 while (head != tail){
87 if (++head == MAXV)
88 head = 0;
89 int u = Q[head];
90 inQ[u] = 0;
91 for (ENode *e=revnet[u]; e; e=e->next){
92 if (revdis[e->ver] > revdis[u] + e->w){
93 revdis[e->ver] = revdis[u] + e->w;
94 if (!inQ[e->ver]){
95 if (++tail == MAXV)
96 tail = 0;
97 Q[tail] = e->ver;
98 inQ[e->ver] = 1;
99 }
100 }
101 }
102 }
103 }
104
105int main(){
106 scanf("%d %d %d", &n, &m, &x);
107 int i;
108 for (i=1; i<m+1; i++){
109 int u, v, w;
110 scanf("%d %d %d", &u, &v, &w);
111 AddEdge(u, v, w);
112 }
113 //
114 Spfa();
115 int ans = 0;
116 for (i=1; i<n+1; i++){
117 ans = gmax(ans, dis[i] + revdis[i]);
118 }
119 printf("%d\n", ans);
120
121 return 0;
122 }
123
那个Compile Error和我没关系。。
还有PKU1119的用G++和C++都没编译通过。。