1460.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1460 on 2005-11-06 at 19:20:32 */ 
#include <cstdio>
#include <cstring>

const int MAX_CITY = 256;
const int MAX_LEN = 32;
const int INFINITE = 100000000;

class BSTNode {
public:
    char name[MAX_LEN];
    BSTNode *left;
    BSTNode *right;
	int order;
	void init(int o, char *s) {
		order = o;
		strcpy(name, s);
		left = right = NULL;
	}
    int search(BSTNode &node) {
        BSTNode *p = this;
        while(true) {
            int i = strcmp(p->name, node.name);
            if(i < 0) {
                if(p->left != NULL) {
                    p = p->left;
                } else {
					p->left = &node;
                    return -1;
                }    
            } else if(i > 0) {
                if(p->right != NULL) {
                    p = p->right;
                } else {
					p->right = &node;
                    return -1;
                }
            } else {
                return p->order;
            }    
        }
    } 
};

class List {
public:
	int path[MAX_CITY];
	int link[MAX_CITY];
	int n;
};

List list[MAX_CITY];
int n;

int Dijkstra(int, int);
inline int max(int, int);
inline int min(int, int);

int main()
{
	BSTNode *root, node[MAX_CITY];
	char name[2][MAX_LEN];
	int r, pn, dis, src, t = 1;
	int i, j, d, o[2];

	while(scanf("%d %d", &n, &r) == 2) {
		if(n == 0 && r == 0) {
			return 0;
		} else {
			for(i = 0; i < n; i++) {
				list[i].n = 0;
			}
			root = NULL;
			pn = 0;
			for(i = 0; i < r; i++) {
				scanf("%s %s %d", name[0], name[1], &d);
				for(j = 0; j < 2; j++) {
					node[pn].init(pn, name[j]);
					if(root == NULL) {
						o[j] = pn;
						root = &node[pn++];
					} else {
						o[j] = root->search(node[pn]);
						if(o[j] == -1) {
							o[j] = pn++;
						}
					}
				}
				list[o[0]].link[list[o[0]].n] = o[1];
				list[o[1]].link[list[o[1]].n] = o[0];
				list[o[0]].path[list[o[0]].n++] = list[o[1]].path[list[o[1]].n++] = d;
			}
			scanf("%s %s", name[0], name[1]);
			node[pn].init(-1, name[0]);
			src = root->search(node[pn++]);
			node[pn].init(-1, name[1]);
			dis = root->search(node[pn++]);
			printf("Scenario #%d\n", t);
			t++;
			printf("%d tons\n\n", Dijkstra(src, dis));
		}
	}
	
	return 0;
}

int Dijkstra(int src, int dis)
{
	int d[MAX_CITY] = {0}, m, maxi = src;
	bool visit[MAX_CITY] = {false};
	int i, j, p;

	for(i = 0; i < n; i++) {
		m = 0;
		for(j = 0; j < n; j++) {
			if(m < d[j] && !visit[j]) {
				m = d[j];
				maxi = j;
			}
		}
		visit[maxi] = true;
		for(j = 0; j < list[maxi].n; j++) {
			if(!visit[list[maxi].link[j]]) {
				if(d[maxi] == 0) {
					p = list[maxi].path[j];
				} else {
					p = min(d[maxi], list[maxi].path[j]);
				}
				d[list[maxi].link[j]] = max(p, d[list[maxi].link[j]]);
			}
		}
		if(maxi == dis) {
			break;
		}
	}
	return d[dis];
}
inline int max(int n, int m)
{
	return n > m ? n : m;
}
inline int min(int n, int m)
{
	return n < m ? n : m;
}