題目描述
C 國有 n 個大城市和 m 條道路，每條道路連接這 n 個城市中的某兩個城市。任意兩個
城市之間最多只有一條道路直接相連。這 m 條道路中有一部分為單向通行的道路，一部分
為雙向通行的道路，雙向通行的道路在統計條數時也計為 1 條。
C 國幅員遼闊，各地的資源分布情況各不相同，這就導致了同一種商品在不同城市的價
格不一定相同。但是，同一種商品在同一個城市的買入價和賣出價始終是相同的。
商人阿龍來到 C 國旅游。當他得知同一種商品在不同城市的價格可能會不同這一信息
之后，便決定在旅游的同時，利用商品在不同城市中的差價賺回一點旅費。設 C 國 n 個城
市的標號從 1~ n，阿龍決定從 1 號城市出發，并最終在 n 號城市結束自己的旅行。在旅游的
過程中，任何城市可以重復經過多次，但不要求經過所有 n 個城市。阿龍通過這樣的貿易方
式賺取旅費：他會選擇一個經過的城市買入他最喜歡的商品――水晶球，并在之后經過的另
一個城市賣出這個水晶球，用賺取的差價當做旅費。由于阿龍主要是來 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 條道路的信息（每條道路所連接的兩個城市的編號
以及該條道路的通行情況）。請你告訴阿龍，他最多能賺取多少旅費。
思路
建兩個圖，一個正著，一個倒著，先跑一邊spfa，邊的權值為出發點的價格，這樣可以求出全部點可以達到的最小進價，然后用倒著的圖跑一邊dfs，求出每一個點是否可以走到終點，最后枚舉一邊，在當前點可以到達終點的情況下，這個點的最大價格就是原價減去最小進價
#include <stdio.h>#include <queue>#include <iostream>#define maxn 500001#define INF 2147483647using namespace std;int l=0,s;struct arr { int x,y,w,next; };int x,y,z;arr edge[maxn],edge1[maxn];int ls[maxn],ls1[maxn];int a[maxn],f[maxn],fl[maxn];int state[maxn];bool exits[maxn];int dfs(int x){ if (x==0) return 0; int i=ls1[x]; while (i!=0) { if(fl[edge1[i].y]==0) { f[edge1[i].y]=1; fl[edge1[i].y]=1; dfs(edge1[i].y); } i=edge1[i].next; } return 0;}int spfa(){ int i; queue <int> t; t.push(1); state[1]=0; exits[1]=true; do { int tt=t.front(); t.pop(); i=ls[tt]; while (i!=0) { if (edge[i].w<state[edge[i].y]) { state[edge[i].y]=edge[i].w; if (exits[edge[i].y]==false) { t.push(edge[i].y); exits[edge[i].y]=true; } } i=edge[i].next; } exits[tt]=false; } while (!t.empty());}int main(){ int j,k,n,m,e; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]); int l=0; for (int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if (z==1) { edge[++l]=(arr){x,y,a[x],ls[x]}; ls[x]=l; edge1[l]=(arr){y,x,0,ls1[y]}; ls1[y]=l; } else { edge[++l]=(arr){x,y,a[x],ls[x]}; ls[x]=l; edge1[l]=(arr){y,x,0,ls1[y]}; ls1[y]=l; edge[++l]=(arr){y,x,a[y],ls[y]}; ls[y]=l; edge1[l]=(arr){x,y,0,ls1[x]}; ls1[x]=l; } } for (int i=1;i<maxn;i++) state[i]=INF; spfa(); dfs(n); int ans=0; for (int i=2;i<=n;i++) { if (state[i]!=INF&&f[i]==1&&a[i]-state[i]>ans) ans=a[i]-state[i]; }
