学步园

http://acm.poj.org/problem?id=1394

求尽可能迟的出发，但又最早到的火车路线

#include<stdio.h><br /> #include<string.h><br /> #define INF 1000001<br /> int C, T;<br /> struct {<br /> int time;<br /> int city;<br /> }map[1000][100];<br /> char name[100][100];<br /> int start, dist;<br /> int train[1000];<br /> int travel[100];<br /> int search(char *city) {<br /> for(int i=0; i<C; i++) {<br /> if(!strcmp(name[i], city))<br /> return i;<br /> }<br /> return -1;<br /> }<br /> void solve(int dep) {<br /> int i, j, k;<br /> for(i=0; i<C; i++) {<br /> travel[i] = INF;<br /> }<br /> travel[start] = dep;<br /> for(k=0; k<C; k++) {<br /> for(i=0; i<T; i++) {<br /> for(j=0; j<train[i]-1; j++) {<br /> if(map[i][j].time >= travel[map[i][j].city] && travel[map[i][j+1].city] > map[i][j+1].time)<br /> travel[map[i][j+1].city] = map[i][j+1].time;<br /> }<br /> }<br /> }<br /> for(i=0; i<C; i++) {<br /> if(i != dist)<br /> travel[i] = -1;<br /> }<br /> for(k=0; k<C; k++) {<br /> for(i=0; i<T; i++) {<br /> for(j=0; j<train[i]-1; j++) {<br /> if(map[i][j+1].time <= travel[map[i][j+1].city] && travel[map[i][j].city] < map[i][j].time)<br /> travel[map[i][j].city] = map[i][j].time;<br /> }<br /> }<br /> }<br /> }<br /> int main() {<br /> //freopen("in.txt", "r", stdin);<br /> int i, j;<br /> char str[1000];<br /> int dep;<br /> int id = 1;<br /> while(scanf("%d", &C), C) {<br /> for(i=0; i<C; i++)<br /> scanf("%s", name[i]);<br /> scanf("%d", &T);<br /> for(i=0; i<T; i++) {<br /> scanf("%d", &train[i]);<br /> for(j=0; j<train[i]; j++) {<br /> scanf("%d%s", &map[i][j].time, str);<br /> map[i][j].city = search(str);<br /> }<br /> }<br /> scanf("%d", &dep);<br /> scanf("%s", str);<br /> start = search(str);<br /> scanf("%s", str);<br /> dist = search(str);<br /> solve(dep);<br /> printf("Scenario #%d/n", id++);<br /> if(travel[dist] < INF) {<br /> printf("Departure %.4d %s/n", travel[start], name[start]);<br /> printf("Arrival %.4d %s/n/n", travel[dist], name[dist]);<br /> } else {<br /> puts("No connection/n");<br /> }<br /> }<br /> return 0;<br /> }