题解 | #I Wanna Go Home#

#include<iostream>
#include<algorithm>

const int MAX = 1024;
const int INF = 1e9;

class Solution
{
    public:
    int n;
    int G[MAX][MAX];
    int position[MAX];
    bool visit[MAX];
    int d[MAX];

    Solution(int n1)
        : n(n1)
    {
        std::fill(visit, visit+MAX, false);
        std::fill(position, position+MAX, -1);
        std::fill(d, d+MAX, INF);
        d[1] = 0;
        //注意对二维数组的初始化
        std::fill(G[0], G[0]+MAX*MAX, INF);
    }

    void Dijkstra()
    {
        for(int i=0;i<n;i++)
        {
            int u = -1, min = INF;
            for(int j=1;j<=n;j++)
            {
                if(!visit[j] && d[j] < min)
                {
                    u = j;
                    min = d[j];
                }
            }
            if(u == -1) return;
            visit[u] = true;
            for(int j=1;j<=n;j++)
            {
                //加一个限制条件，只准从1到2，不准从2到1
                if(!(position[u]==2 && position[j]==1))
                {
                    if(!visit[j] && G[u][j]!=INF && d[u]+G[u][j] < d[j])
                    {
                        d[j] = d[u]+G[u][j];
                    }
                }
            }
        }
    }
};

int main()
{
    int n, m;
    while (std::cin >> n)
    {
        if(n==0) break;
        std::cin >> m;
        Solution* s = new Solution(n);;
        for(int i=0;i<m;i++)
        {
            int A, B, T;
            std::cin >> A >> B >> T;
            if(s->G[A][B] > T)
            {
                s->G[A][B] = T;
                s->G[B][A] = T;
            }
        }
        for(int i=1;i<=n;i++)
        {
            std::cin >> s->position[i];
        }
        s->Dijkstra();

        if(s->d[2]!=INF)
            std::cout << s->d[2] << std::endl;
        else
            std::cout << -1 << std::endl;
        
        delete s;
    }
    
}