1598.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 61 行

/*  This Code is Submitted by wywcgs for Problem 1598 on 2006-03-14 at 14:24:36 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 10;
const int INF = 1 << 28;

class City {
private:
	vector<int> plane[MAX];
public:
	int o;
	void make(int);
	int go(int co, int day) const { return plane[co][day%plane[co].size()]; }
};
void City::make(int cn) {
	int i, j;
	for(i = 0; i < cn; i++) {
		if(i == o) continue;
		int n; scanf("%d", &n);
		plane[i].clear();
		for(j = 0; j < n; j++) {
			int a; scanf("%d", &a);
			plane[i].push_back((a == 0) ? INF : a);
		}
	}
}

inline int min(int a, int b) { return a > b ? b : a; }

int main()
{
	int n, m, cost[MAX];
	int i, j, k, t;
	City city[MAX];

	for(i = 0; i < MAX; i++) city[i].o = i;
	for(t = 1; scanf("%d %d", &n, &m) != EOF && n != 0; t++) {
		for(i = 0; i < n; i++) { city[i].make(n); cost[i] = INF; }
		cost[0] = 0;
		for(i = 0; i < m; i++) {
			int nxt[MAX];
			for(j = 0; j < n; j++) {
				nxt[j] = INF;
				for(k = 0; k < n; k++) {
					if(j == k) continue;
					nxt[j] = min(nxt[j], cost[k]+city[k].go(j, i));
				}
			}
			memcpy(cost, nxt, sizeof(nxt));
		}
		printf("Scenario #%d\n", t);
		if(cost[n-1] == INF) printf("No flight possible.\n\n");
		else printf("The best flight costs %d.\n\n", cost[n-1]);
	}

	return 0;
}