题解 | #I Wanna Go Home#

#include <iostream>
#include <string>
#include <vector>
#include<queue>
using namespace std;

const int INF = 1e6;
const int MAXN = 1e3;

struct Edge
{
	int from, to, weight;
	Edge(int a, int b, int c)
	{
		from = a, to = b, weight = c;
	}
};
struct Node
{
	int index, dis;
	Node(int a, int b)
	{
		index = a, dis = b;
	}
	friend bool operator<(Node a, Node b)
	{
		return a.dis > b.dis;
	}
};

vector<Edge>Adj[MAXN];
int learder[MAXN];
int dist[MAXN];
bool visited[MAXN];
void initConfig()
{
	fill(learder, learder + MAXN, -1);
	fill(dist, dist + MAXN, INF);
	fill(visited, visited + MAXN, false);
	for (int i = 0; i < MAXN; i++)
	{
		Adj[i].clear();
	}
}

void Dijstra(int S, int T)
{
	priority_queue<Node>q;
	dist[S] = 0;
	q.push(Node(S, dist[S]));
	while (q.empty() == false)
	{
		Node node = q.top(); q.pop();
		if (visited[node.index] !=false ) continue;
		visited[node.index] = true;
		for (int i = 0; i < Adj[node.index].size(); i++)
		{
			Edge e = Adj[node.index][i];
			if (visited[e.to] != false) continue;
			if (dist[e.to] > dist[e.from] + e.weight)
			{
				dist[e.to] = dist[e.from] + e.weight;
				q.push(Node(e.to, dist[e.to]));
			}
		}
	}
}

int main() 
{
	int N, M;	
	while (scanf("%d", &N)!=EOF)
	{
		if (N == 0)
		{
			break;
		}
		scanf("%d", &M);
		initConfig();
		for (int i = 0; i < M; i++)
		{
			int from, to, weight;
			scanf("%d %d %d", &from, &to, &weight);
			Adj[from].push_back(Edge(from, to, weight));
			Adj[to].push_back(Edge(to, from, weight));
		}
		for (int i = 1; i <= N; i++)
		{
			scanf("%d", &learder[i]);
		}
		for (int i = 0; i < MAXN; i++)
		{
			for (int j = 0; j < Adj[i].size();)
			{
				int from = Adj[i][j].from;
				int to = Adj[i][j].to;
				if (learder[from] == 2 && learder[to] == 1)
				{
					Adj[i].erase(Adj[i].begin() + j);
				}
				else
				{
					j++;
				}
			}
		}
		Dijstra(1, 2);
		if (dist[2] != INF)
		{
			cout << dist[2] << endl;
		}
		else
		{
			cout << -1 << endl;
		}


	}



}