题解 | #I Wanna Go Home#

#include <queue>
#include <iostream>
#include <vector>
using namespace std;
const int maxn=1000;
const int MAX=10000;
struct edge{
    int to;
    int length;
    edge(int a,int b):to(a),length(b){};
};
struct city{
    int number;
    int dis;
    int leader;
    city(int number,int dis,int leader):number(number),dis(dis),leader(leader){};
    bool operator<(city y) const{
        return dis>y.dis;
    }
};
vector<edge> G[maxn];
priority_queue<city> q;
int dist[maxn];
int lead[maxn];
void init(){
    for(int i=0;i<maxn;i++){
        G[i].clear();
        lead[i]=0;
        dist[i]=MAX;
    }
    while(!q.empty()) q.pop();
}
bool IfCanPass(int x,int y){
    if(lead[x]==lead[y]) return true;
    else if(lead[x]==1 && lead[y]==2) return true;
    else return false;
}
int main(){
    int n;
    while(cin>>n && n!=0){
        init();
        int m;
        cin>>m;
        for(int i=0;i<m;i++){
            int a,b,c;
            cin>>a>>b>>c;
            G[a].push_back(edge(b,c));
            G[b].push_back(edge(a,c));
        }
        for(int i=1;i<=n;i++){
            int ld;
            cin>>ld;
            lead[i]=ld;
        }
        q.push(city(1,0,1));
        dist[1]=0;
        while(!q.empty()){
            city tem=q.top();
            q.pop();
            for(int i=0;i<G[tem.number].size();i++){
                edge t=G[tem.number][i];
                if(dist[t.to]>dist[tem.number]+t.length &&
                IfCanPass(tem.number, t.to)){
                    dist[t.to]=dist[tem.number]+t.length;
                    q.push(city(t.to,dist[t.to],lead[t.to]));
                }
            }
        }
        if(dist[2]==MAX) cout<<"-1"<<endl;
        else cout<<dist[2]<<endl;


    }
}