题意抽象:在一张特殊的图上, 有a条正常边, b条特殊边, 输出只使用一条特殊边到达终点的最短距离.
做法:拆点, 把dist数组和st数组全都拆成两维, 第一维表示还没有用过特殊边, 第二维表示已经用过特殊边, 然后跑dijkstra的时候, 将使用过特殊边的情况随着节点编号和距离一起推入堆中, 让后续边遍历的时候继承之前是否用过特殊边的情况
#include <bits/stdc++.h>
using namespace std;
const int N = 1000, M = 1e5;
typedef pair<int, pair<int, int>> PII;
#define x first
#define y second
int h[N], e[M], w[M], ne[M], idx;
int dist[N][2];
int type[N];
bool st[N][2];
int n, m;
void add(int a, int b, int c) // 添加一条边a->b,边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra() // 求1号点到n号点的最短路距离
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[1][0] = 0; //1号点且没有使用过特殊边的dist才置为0
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, {1, 0}}); // {距离, {节点编号, 是否使用过特殊边}}
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y.x, tt = t.y.y; //tt表示是否使用过特殊边
if (st[ver][tt]) continue;
st[ver][tt] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if(type[j] != type[ver]){ //如果阵营不同, 也就是说该边是特殊边
if(tt) continue; //如果已经用过特殊边就跳过
else{
if(dist[j][1] > dist[ver][0] + w[i]){ //没有用过特殊边, dist[j][1]应该由dist[ver]的没有用过特殊边的情况继承过来
dist[j][1] = dist[ver][0] + w[i];
heap.push({dist[j][1], {j, 1}});
}
}
}
else{
if(dist[j][tt] > dist[ver][tt] + w[i]){ //正常dijkstra
dist[j][tt] = dist[ver][tt] + w[i];
heap.push({dist[j][tt], {j, tt}});
}
}
}
}
}
int main()
{
while(scanf("%d", &n), n){
memset(h, -1, sizeof h);
idx = 0;
scanf("%d", &m);
while (m -- ){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
for(int i = 1; i <= n; i ++ ){
scanf("%d", &type[i]);
}
dijkstra();
if(dist[2][1] == 0x3f3f3f3f) puts("-1");
else printf("%d\n", dist[2][1]);
}
return 0;
}
tql