题解 | #I Wanna Go Home#

/*
只要在dijkstra遍历的时候加一个限制条件就行:不能从阵营2走到阵营1
脑瓜子清醒的时候写的，一遍过
*/

#include <climits>
#include<iostream>
#include<queue>
#include <algorithm>
#include<cstring>
using namespace std;

const int INF=INT_MAX;

struct Point
{
    int id;
    int distance;
    int zy;
    Point (int i,int d,int z)
    {
        id=i;
        distance=d;
        zy=z;
    }
    bool operator<(const Point& p)const
    {
        return distance>p.distance;
    }
};

struct Edge
{
    int to;
    int len;
    Edge(int t,int l)
    {
        to=t;
        len=l;
    }
};

vector<Edge> graph[20001];
int dis[601];
int ZY[601];

void Dijkstra(int s)
{
    priority_queue<Point> q;
    dis[s]=0;
    q.push(Point(s,0,ZY[s]));

    while(!q.empty())
    {
        int v=q.top().id;
        q.pop();
        for(int i=0;i<graph[v].size();i++)
        {
            int t=graph[v][i].to;
            int l=graph[v][i].len;
            int fz=ZY[v];
            int tz=ZY[t];
            if((dis[v]+l<dis[t])&&!(fz==2&&tz==1))
            {
                dis[t]=dis[v]+l;
                q.push(Point(t,dis[t],tz));
            }
        }
    }
}

int main()
{
    
    int n,m;
    while(cin>>n)
    {
        if(n==0)break;
        memset(graph,0,sizeof(graph));
        fill(dis,dis+601,INF);
        fill(ZY,ZY+601,0);

        cin>>m;
        for(int i=1;i<=m;i++)
        {
            int a,b,length;
            cin>>a>>b>>length;
            graph[a].push_back(Edge(b,length));
            graph[b].push_back(Edge(a,length));
        }
        for(int i=1;i<=n;i++)
        {
            cin>>ZY[i];
        }

        int ans=0;
        Dijkstra(1);
        ans=dis[2];
        if(ans==INF)cout<<"-1"<<endl;
        else cout<<ans<<endl;

    }
    return 0;
}