A. 最优贸易
Description
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 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
Input
第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。
接下来 m 行，每行有 3 个正整数，x,y,z，每两个整数之间用一个空格隔开。如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市y 之间的双向道路。
1≤n≤100000，1≤m≤500000，1≤x,y≤n，1≤z≤2，1≤各城市水晶球价格≤100。
Output
输出共 1 行，包含 1 个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出 0。
Samples
Input
5 5 4 3 5 6 1 1 2 1 1 4 1 2 3 2 3 5 1 4 5 2
Output
5
大致方法：
看懂题目意思之后可以知道有多种状态，买和卖的关系，这样就可以用分层图最短路。
在建边的时候，假设建立多层，对于本题，首先要建立原始的一层，然后有买的一层，然后还要有卖的一层，这个时候就是要建立三层
这个题来讲，对于两点的关系：在同一层之间建立边权为0的关系
在另外的两层中，同层之间也是建立边权为0的边。在两层之间建立边权为正的一条边，在另外两层之间建立边权为负数的边
在建立关系的过程中，要在相邻的层之间建立
void _addEdge(int x,int y){ add(x,y,0);/// val == 0 add(x+n,y+n,0);/// another floor add(x+2*n,y+2*n,0);/// another floor add(x,y+n,-1 * val[x]);/// between two floor + add(x+n,y+2*n,val[x]);/// between two floor - }
const int maxn = 1e6+7; int n; int m; int val[maxn << 1]; int head[maxn << 1]; bool vis[maxn << 1]; int cnt = 0; struct node { int u,v,w; int nex; } e[maxn]; int dis[maxn << 1]; void add(int u,int v,int w) { e[cnt].v = v; e[cnt].w = w; e[cnt].nex = head[u]; head[u] = cnt++; } void init() { for(int i=1; i<=3*n; i++) { head[i] = -1; dis[i] = -999999; vis[i] = 0; } } void _addEdge(int x,int y){ add(x,y,0);/// val == 0 add(x+n,y+n,0);/// another floor add(x+2*n,y+2*n,0);/// another floor add(x,y+n,-1 * val[x]);/// between two floor + add(x+n,y+2*n,val[x]);/// between two floor - } /// < struct cmp{ bool operator()(int a,int b) { return dis[a] < dis[b]; } }; void spfa(int x){ queue<int> que; que.push(x); vis[x] = 1;dis[x] = 0;/// visit the pnt while(que.size()){ int u = que.front();que.pop(); vis[u] = false; for(int i=head[u];~i;i = e[i].nex){ int v = e[i].v; if(dis[v] < dis[u] + e[i].w){ dis[v] = dis[u] + e[i].w; if(vis[v] == 0){ vis[v] = 1; que.push(v); } } } } } int main() { n = read,m=read; init(); for(int i=1;i<=n;i++) val[i] = read; for(int i=1;i<=m;i++){ int u=read,v=read,op=read; _addEdge(u,v); if(op == 2) _addEdge(v,u); } ///add(n,2*n,0),add(2*n,3*n,0); spfa(1); cout<<max(dis[n],dis[3*n])<<'\n'; return 0; }
B. 道路和航线
Description
Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到T
个城镇 (1≤T≤25,000)，编号为1T。这些城镇之间通过R条道路 (1≤R≤50,000，编号为1到R) 和P条航线 (1≤P≤50,000，编号为1到P) 连接。每条道路i或者航线i连接城镇Ai (1≤Ai≤T)到Bi (1≤Bi≤T)，花费为Ci。对于道路，0≤Ci≤10,000; 然而航线的花费很神奇，花费Ci可能是负数(−10,000≤Ci≤10,000)。道路是双向的，可以从Ai到Bi，也可以从Bi到Ai，花费都是Ci。然而航线与之不同，只可以从Ai到Bi。事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台 了一些政策保证：如果有一条航线可以从Ai到Bi，那么保证不可能通过一些道路和航线从Bi回到Ai。由于FJ的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1≤S≤T) 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。
Input
第1行：四个空格隔开的整数: T,R,P, and S
第2到R+1行：三个空格隔开的整数（表示一条道路）：Ai,Bi 和 Ci
第R+2
到R+P+1行：三个空格隔开的整数（表示一条航线）：Ai,Bi 和 Ci
Output
第1到T行：从S到达城镇i的最小花费，如果不存在输出"NO PATH"。
Samples
Input 复制
6 3 3 4 1 2 5 3 4 5 5 6 10 3 5 -100 4 6 -100 1 3 -10
Output
NO PATH NO PATH 5 0 -95 -100
Hint
一共六个城镇。在1-2，3-4，5-6之间有道路，花费分别是5，5，10。同时有三条航线：3->5，
4->6和1->3，花费分别是-100，-100，-10。FJ的中心城镇在城镇4。
FJ的奶牛从4号城镇开始，可以通过道路到达3号城镇。然后他们会通过航线达到5和6号城镇。
但是不可能到达1和2号城镇。
通过题意可以很轻松的了解到这是个最短路问题
因为存在负数，所以要注意负环的问题，但是题目中说到事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台 了一些政策保证：如果有一条航线可以从Ai到Bi，那么保证不可能通过一些道路和航线从Bi回到Ai，所以就不存在负环的现象
但是如果用单纯的SPFA会被卡TLE，这个时候要用到SPFA的双端队列优化或者是尝试其他方法，这里采用SPFA的双端队列优化
如果说当前节点不在队列里面，并且这个点的最短距离小于队列头端点的距离，就可以放到队列的前端，否则就放到队列的末端
const int maxn = 1e6+7; int t,r,p,s; struct node{ int u; int v; int nex; int w; }e[maxn]; int cnt = 0; int head[maxn]; int vis[maxn]; int dis[maxn]; void init(){ for(int i=1;i<=(t<<1);i++) { vis[i] = 0; dis[i] = 0x3f3f3f3f; head[i] = -1; } } void add(int x,int y,int w){ e[cnt].u = x; e[cnt].v = y; e[cnt].w = w; e[cnt].nex = head[x]; head[x] = cnt ++; } void spfa(int x){ ///queue<int> que; deque<int>que; que.push_back(x); dis[x] = 0; /// vis[x] = 1; while(que.size()){ int u = que.front(); que.pop_front(); vis[u] = 0; for(int i=head[u];~i;i = e[i].nex){ int to = e[i].v; if(dis[to] > dis[u] + e[i].w){ dis[to] = dis[u] + e[i].w; if(!vis[to]){ vis[to] = 1; ///que.push(to); if(que.size() && dis[to] < dis[que.front()]) que.push_front(to); else que.push_back(to); } } } } } int main() { /// freopen("1.in","r",stdin); cin >> t >> r >> p >> s; init(); for(int i=1;i<=r;i++){ int x=read,y=read,w=read; add(x,y,w); add(y,x,w); } for(int i=1;i<=p;i++){ int x=read,y=read,w=read; add(x,y,w); } /// puts("ok"); spfa(s); for(int i=1;i<=t;i++){ if(dis[i] == 0x3f3f3f3f) puts("NO PATH"); else printf("%d\n",dis[i]); } return 0; }
