题解 | #I Wanna Go Home#

#include <climits>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Edge{
    int to,w;
    Edge(int x, int y): to(x), w(y) {};
};

struct Point{
    int p,d;
    Point(int x, int y): p(x), d(y) {};

    bool operator < (const Point &po) const{
        return d > po.d;//用大根堆实现小根堆
    }
};

const int N = 610;
const int INF = INT_MAX;
int st[N];
int dist[N];

vector<Edge> g[N];//邻接表

void init(int n){
    for(int i=1;i<=n;i++){
        dist[i]=INF;
        g[i].clear();
    }
    dist[1]=0;
}

/*dijie什么时候确定一条边是要加入到最小生成树里呢？：
在小根堆弹出对头元素时，加入的边是对头元素与最小生成树某一结点的边。

限制条件：选入的边，只能从阵营1到阵营2，不能存在从阵营2到阵营1
因为：不能从阵营2到阵营1，而起点在阵营1，终点在阵营2，故只选择了一条从阵营1到阵营2的边。
*/

void dijie(int n){
    priority_queue<Point> heap;
    heap.push(Point(1,0));
    while(heap.size()){
        Point t = heap.top();
        heap.pop();
        int u = t.p;
        for(int i=0;i<g[u].size();i++){
            int v = g[u][i].to;
            int l = g[u][i].w;
            if(st[v]==1&&st[u]==2)continue;
            if(dist[u]+l<dist[v]){
                dist[v]=dist[u]+l;
                heap.push(Point(v,dist[v]));
            }
        }
    }
    return;

}


int main(){
    int n;
    while(cin>>n){
        if(!n)break;
        init(n);
        int m;
        cin>>m;
        while(m--){
            int a,b,w;
            cin>>a>>b>>w;
            g[a].push_back(Edge(b,w));
            g[b].push_back(Edge(a,w));
        }
        for(int i=1;i<=n;i++){
            cin>>st[i];
        }
        dijie(n);
        int ans = dist[2]==INF? -1:dist[2];
        cout<<ans<<endl;
    }
    return 0;
}