1173 最优贸易
2009年NOIP全国联赛提高组
C 国有n 个大城市和m 条道路，每条道路连接这n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。
C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。
假设 C 国有5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。
假设 1~n 号城市的水晶球价格分别为4，3，5，6，1。
阿龙可以选择如下一条线路：1->2->3->5，并在2 号城市以3 的价格买入水晶球，在3号城市以5 的价格卖出水晶球，赚取的旅费数为2。
阿龙也可以选择如下一条线路 1->4->5->4->5，并在第1 次到达5 号城市时以1 的价格买入水晶球，在第2 次到达4 号城市时以6 的价格卖出水晶球，赚取的旅费数为5。
现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
第一行包含 2 个正整数n 和m，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这n 个城市的商品价格。
接下来 m 行，每行有3 个正整数，x，y，z，每两个整数之间用一个空格隔开。如果z=1，表示这条道路是城市x 到城市y 之间的单向道路；如果z=2，表示这条道路为城市x 和城市y 之间的双向道路。
包含1 个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出0。
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
5
【数据范围】
输入数据保证 1 号城市可以到达n 号城市。
对于 10%的数据，1≤n≤6。
对于 30%的数据，1≤n≤100。
对于 50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。
对于 100%的数据，1≤n≤100000，1≤m≤500000，1≤x，y≤n，1≤z≤2，1≤各城市
水晶球价格≤100。
分析 Analysis
这道题也算是冷饭了吧。（虽然当时直接放弃了）
首先确定一点：这个图难以避免死路。万一主人公走到某些出不来的地方那就更别谈贸易了，因此首先确定源点终点两遍SPFA求有效点。
第二步比较坑，是求差价。一开始我绕进了暴力的坑里（每个点一次SPFA结果果真TLE了）
真 - TLE自动机！
后来可能稍稍地看了下别人的题解，恍然大悟：其实可以在刚开始那两遍SPFA的过程中顺便维护当主人公到达各个城市已经遭遇过的最高/最低价格，这样最后再来一次O(n)枚举就行了。
也就是说，把这个可能的最大价格和最小价格当作结点的附带信息。
代码 Code
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define maxn 1000000 5 using namespace std; 6 7 struct edge{ 8 int v,from; 9 }e1[maxn],e2[maxn]; 10 11 int first1[maxn],first2[maxn],tot1,tot2; 12 13 int minn(int a,int b){ 14 return a<b?a:b; 15 } 16 17 int minnn(int a,int b,int c){ 18 return minn(a,minn(b,c)); 19 } 20 21 int mx(int a,int b){ 22 return a>b?a:b; 23 } 24 25 int maxxx(int a,int b,int c){ 26 return mx(a,mx(b,c)); 27 } 28 29 void insert(int u,int v){ 30 tot1++; 31 e1[tot1].from = first1[u]; 32 e1[tot1].v = v; 33 first1[u] = tot1; 34 35 tot2++; 36 e2[tot2].from = first2[v]; 37 e2[tot2].v = u; 38 first2[v] = tot2; 39 } 40 41 int a,b,c,prize[maxn],minpri[maxn],maxpri[maxn]; 42 int dis[maxn],que[maxn],head,tail,lag[maxn],n,m; 43 bool book[maxn]; 44 45 void STEP1(){ 46 for(int i = 1;i <= n;i++){ 47 dis[i] = 999999999; 48 minpri[i] = 999999999; 49 } 50 memset(book,false,sizeof(book)); 51 tail = 0,head = 0; 52 53 que[head++] = 1; 54 book[1] = true; 55 dis[1] = 0; 56 57 while(tail < head){ 58 int p = que[tail]; 59 60 for(int i = first1[p];i;i = e1[i].from){ 61 minpri[e1[i].v] = minnn(prize[e1[i].v],minpri[e1[i].v],minpri[p]); 62 if(dis[e1[i].v] > dis[p]){ 63 64 dis[e1[i].v] = dis[p]; 65 if(!book[e1[i].v]){ 66 que[head++] = e1[i].v; 67 book[e1[i].v] = true; 68 } 69 } 70 } 71 72 book[p] = 0; 73 tail++; 74 } 75 76 for(int i = 1;i <= n;i++){ 77 if(!dis[i]) lag[i]++; 78 } 79 80 for(int i = 1;i <= n;i++) dis[i] = 999999999; 81 tail = 0,head = 0; 82 83 que[head++] = n; 84 book[n] = true; 85 dis[n] = 0; 86 87 while(tail < head){ 88 int p = que[tail]; 89 90 for(int i = first2[p];i;i = e2[i].from){ 91 maxpri[e2[i].v] = maxxx(maxpri[e2[i].v],maxpri[p],prize[e2[i].v]); 92 if(dis[e2[i].v] > dis[p]){ 93 94 dis[e2[i].v] = dis[p]; 95 if(!book[e2[i].v]){ 96 que[head++] = e2[i].v; 97 book[e2[i].v] = true; 98 } 99 } 100 } 101 102 book[p] = 0; 103 tail++; 104 } 105 106 for(int i = 1;i <= n;i++){ 107 if(!dis[i]) lag[i]++; 108 } 109 } 110 111 int main(){ 112 scanf("%d%d",&n,&m); 113 114 for(int i = 1;i <= n;i++) 115 scanf("%d",&prize[i]); 116 117 for(int i = 0;i < m;i++){ 118 scanf("%d%d%d",&a,&b,&c); 119 insert(a,b); 120 if(c%2 == 0) insert(b,a); 121 } 122 123 STEP1(); 124 125 int maxx = 0; 126 127 for(int i = 1;i <= n;i++){ 128 if(lag[i] == 2){ 129 maxx = mx(maxx,maxpri[i]-minpri[i]); 130 } 131 } 132 133 // for(int i = 1;i <= n;i++){ 134 // printf("%d/%d ",maxpri[i],minpri[i]); 135 // } 136 137 // cout << endl; 138 139 printf("%d",maxx); 140 141 return 0; 142 }