4082958_wa.cc

北大大牛代码 1240道题的原代码 超级权威

#include <vector>
#include <stdio.h>
#include <algorithm>

using namespace std;

struct node
{
	int tar, cost;
};

vector <node> map[70];
const int inf = 0xfffffff;

int main()
{
	int n, m;
	int u, v;
	int cost;
	int now;
	
	now = 1;
	while (true)
	{
		scanf("%d%d", &n, &m);
		if (n == 0 && m == 0)
		{
			break;
		}
		printf("Instance #%d: ", now++);
		for (int i = 0; i < n; i++)
		{
			map[i].clear();
		}
		for (int i = 0; i < m; i++)
		{
			scanf("%d%d%d", &u, &v, &cost);
			map[u].push_back((node){v, cost});
		}
		int *dist = new int[n];
		int *prev = new int[n];
		bool*find = new bool[n];
		int *c = new int[n];
		fill_n(dist, n, inf);
		fill_n(find, n, false);
		dist[0] = 0;
		prev[0] = -1;
		while (!find[n - 1])
		{
			int max = inf;
			int pos = -1;
			for (int i = 0; i < n; i++)
			{
				if (find[i] == false && dist[i] < max)
				{
					max = dist[i];
					pos = i;
				}
			}
			if (pos == -1)
			{
				break;
			}
			//printf("%d\n", pos);
			find[pos] = true;
			for (int i = 0; i < map[pos].size(); i++)
			{
				int tmp = dist[pos] + map[pos][i].cost; 
				if (tmp < dist[map[pos][i].tar])
				{
					dist[map[pos][i].tar] = tmp;
					prev[map[pos][i].tar] = pos;
					c[map[pos][i].tar] = map[pos][i].cost;
				}
			}
		}
		if (!find[n - 1])
		{
			puts("Not possible");
			continue;
		}
		int ans = dist[n - 1];
		u = n - 1;
		while (prev[u] != -1)
		{
			int v = prev[u];
			for (vector<node>::iterator it = map[v].begin(); it != map[v].end(); it++)
			{
				if (it->tar == u && it->cost == c[u])
				{
					map[v].erase(it);
					break;
				}
			}
			u = v;
		}
		fill_n(dist, n, inf);
		fill_n(find, n, false);
		dist[0] = 0;
		while (!find[n - 1])
		{
			int max = inf;
			int pos = -1;
			for (int i = 0; i < n; i++)
			{
				if (find[i] == false && dist[i] < max)
				{
					max = dist[i];
					pos = i;
				}
			}
			if (pos == -1)
			{
				break;
			}
			find[pos] = true;
			for (int i = 0; i < map[pos].size(); i++)
			{
				int tmp = dist[pos] + map[pos][i].cost; 
				if (tmp < dist[map[pos][i].tar])
				{
					dist[map[pos][i].tar] = tmp;
				}
			}
		}
		if (!find[n - 1])
		{
			puts("Not possible");
			continue;
		}
		printf("%d\n", ans + dist[n - 1]);
	}
	return 0;
}