题目描述
N个虫洞，M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。
1.从白洞跃迁到黑洞，消耗的燃料值减少delta，若该条路径消耗的燃料值变为负数的话，取为0。
2.从黑洞跃迁到白洞，消耗的燃料值增加delta。
3.路径两端均为黑洞或白洞，消耗的燃料值不变化。
作为压轴题，自然不会是如此简单的最短路问题，所以每过1单位时间黑洞变为白洞，白洞变为黑洞。在飞行过程中，可以选择在一个虫洞停留1个单位时间，如果当前为白洞，则不消耗燃料，否则消耗s[i]的燃料。现在请你求出从虫洞1到N最少的燃料消耗，保证一定存在1到N的路线。 2017-5-8
输入
第1行：2个正整数N,M
第2行：N个整数，第i个为0表示虫洞i开始时为白洞，1表示黑洞。
第3行：N个整数，第i个数表示虫洞i的质量w[i]。
第4行：N个整数，第i个数表示在虫洞i停留消耗的燃料s[i]。
第5..M+4行：每行3个整数，u,v,k，表示在没有影响的情况下，从虫洞u到虫洞v需要消耗燃料k。
输出
一个整数，表示最少的燃料消耗。
样例输入
4 5
1 0 1 0
10 10 100 10
5 20 15 10
1 2 30
2 3 40
1 3 20
1 4 200
3 4 200
样例输出
130
提示
【数据范围】
对于30%的数据：
1<=N<=100,1<=M<=500
对于60%的数据： 1<=N<=1000,1<=M<=5000
对于100%的数据： 1<=N<=5000，1<=M<=30000 其中20%的数据为1<=N<=3000的链 1<=u,v<=N, 1<=k,w[i],s[i]<=200
【样例说明】 按照1->3->4的路线。
思路
这道题看上去很麻烦，其实也很简单，关键就在建图上，然后直接跑最短路：
我们把图分成两层，第一层是时间为偶数的，即这一层的虫洞是跟原来的一样的，第二层是时间为奇数的，即这一层的虫洞是跟原来相反的。
然后我们所有的边都在这两层图之间建立。
那该怎么建立呢？
我们把第二张图的第\(i\)个点放到数组的\(i+n\)的位置，然后就可以建图了。
这里如果建边要注意建两条边：一条是从第一层到第二层的，一条是第二层到第一层的，然后判断一下黑洞还是白洞来调整边长。
如果不动的话，也是要将两条边：跟上面一样，一条是从第一层到第二层的，一条是第二层到第一层的，但要注意白洞到黑洞是不用燃料的，即边权为\(0\)。
最后\(dijkstra\)一下就好了，注意答案可以在黑洞上也可以在白洞上，所以答案是\(\max\lbrace dist_i,dist_{i+n}\rbrace\)
代码
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef pair <int,int> PII;
const int N = 10010,M = 70010;
int n,m;
int type[N],we[N];
int s[N];
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
void add (int a,int b,int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int dijkstra () {
priority_queue <PII,vector <PII>,greater <PII> > heap;
heap.push ({0,1});
memset (dist,0x3f,sizeof (dist));
dist[1] = 0;
while (heap.size ()) {
int t = heap.top ().second;
heap.pop ();
if (st[t]) continue;
st[t] = true;
for (int i = h[t];~i;i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
heap.push ({dist[j],j});
}
}
}
return min (dist[n],dist[2 * n]);
}
int main () {
memset (h,-1,sizeof (h));
cin >> n >> m;
for (int i = 1;i <= n;i++) {
cin >> type[i];
type[i + n] = !type[i];
}
for (int i = 1;i <= n;i++) {
cin >> we[i];
we[i + n] = we[i];
}
for (int i = 1;i <= n;i++) {
cin >> s[i];
s[i + n] = s[i];
}
while (m--) {
int a,b,c;
cin >> a >> b >> c;
if (type[a] != type[b]) {
if (!type[a] && type[b]) add (a,b + n,max (c - abs (we[a] - we[b]),0)),add (a + n,b,c + abs (we[a] - we[b]));
else add (a,b + n,c + abs (we[a] - we[b])),add (a + n,b,max (c - abs (we[a] - we[b]),0));
}
else add (a,b + n,c),add (a + n,b,c);
}
for (int i = 1;i <= n;i++) {
if (!type[i]) add (i,i + n,0),add (i + n,i,s[i]);
else add (i,i + n,s[i]),add (i + n,i,0);
}
cout << dijkstra () << endl;
return 0;
}