minimum transport cost(最短路+字典序最小路径).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int n;
int map[110][110];
int orimap[110][100];
int tax[110];
int ps, path[110];

void floyd()
{
	int i,j,k;
	for(k=0;k<n;k++) {
		for(i=0;i<n;i++) {
			if(map[i][k] != -1) {
				for(j=0;j<n;j++) {
					if(map[k][j] != -1) {
						int cost = map[i][k] + map[k][j] + tax[k];
						if(map[i][j] == -1 || map[i][j] > cost) {
							map[i][j] = cost;
						}
					}
				}
			}
		}
	}
}

void find_path(int s,int e, int c)
{
	int i;
	for(i=0;i<n;i++) {
		if(orimap[s][i] == -1 || map[i][e] == -1) {
			continue ;
		}
		if(orimap[s][i] + map[i][e] + tax[i] == c) {
			printf("-->%d", i+1);
			find_path(i,e,map[i][e]);
			break;
		}
		else if(i == e && orimap[s][e] == c) {
			printf("-->%d", e+1);
			break;
		}
	}
}

void print_path(int s,int e, int c)
{
	int i;
	printf("Path: %d", s+1);
	if(s == e) {
		printf("\n");
		return ;
	}
	find_path(s, e, c);
	printf("\n");
}

int main()
{
	int i,j;
	int s,e;
	while(scanf("%d", &n), n) {
		for(i=0;i<n;i++) {
			for(j=0;j<n;j++) {
				scanf("%d", &map[i][j]);
				orimap[i][j] = map[i][j];
			}
		}
		for(i=0;i<n;i++) {
			scanf("%d", &tax[i]);
		}
		floyd();
		while(scanf("%d %d", &s,&e)==2) {
			if(s == -1 && e == -1) {
				break;
			}
			int mmin = map[s-1][e-1];
			printf("From %d to %d :\n",s,e);
			print_path(s-1,e-1,mmin);
			printf("Total cost : %d\n\n", mmin);
		}
	}
}