无聊发一题。
Code must be ANSI Standard C.
Problem
The empire has a capitol and a number of cities. Some cities are connected to other cities. A route
connecting two cities can transport a message in both directions. All cities are reachable using some path
from the capitol city. The connections among all cities are described in an adjacency matrix with the format
shown below. At the start, a message is sent from the capitol city to all other cities, and we want to know
what’s the minimal time for a message to spread out from the capitol to the whole empire.
Input (Adjacency Matrix)
The first line of the input file will be n, the number of cities, 1 <= n <= 100. The rest of the input defines
an adjacency matrix, A. The adjacency matrix is square and of size n×n. The value of A(i, j) indicates the
time required to travel from city i to city j. A value of character ‘x’ for A(i, j) indicates that there is no route
between city i to city j. Since a message sent to itself doesn’t require time, and the route between cities is
two way, we always have A(i, i) = 0 and A(i, j) = A(j, i). Thus only the entries on the (strictly) lower
triangular portion of A will be supplied as input, and the second line of input will contain one entry, A(2, 1).
The next line will contain two entries, A(3, 1) and A(3, 2), and so on.
Output
Your program should output the minimum time required before a message sent from the capitol (city #1) is
known throughout the empire, i.e. the time it is received in the last city to get the message.
Sample Input
5
50
30 5
100 20 50
10 x x 10
Output for the Sample Input
35
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include <stdio.h> #include <memory.h> #ifndef bool #define bool int #define true 1 #define false 0 #endif #define LIMIT 100 void get_data(int num, int *pdata) { int i, j; for(i = 1; i != num; ++i) { for(j = 0; j != i; ++j) { if(scanf("%d", pdata + i * num + j) != 1) { scanf("%*s"); pdata[i * num + j] = -1; //-1 stands for infinite. pdata[j * num + i] = -1; } else pdata[j * num + i] = pdata[i* num + j]; } } } bool spread(int *pdata, bool *pmark, int city_num, int *time) { int i, j; unsigned mintime = -1; //Init with a max value. bool tmpmark[LIMIT]; for(i = 0; i != city_num; ++i) { if(pmark[i]) { for(j = 0; j < city_num; ++j) { int tmp = pdata[i*city_num + j]; if(tmp > 0 && tmp <= mintime) { mintime = tmp; } } } } if(mintime == -1) return false; memcpy(tmpmark, pmark, city_num * sizeof(bool)); for(i = 0; i != city_num; ++i) { if(pmark[i]) { for(j = 0; j < city_num; ++j) { if(pdata[i*city_num + j] > 0) { pdata[i*city_num + j] -= mintime; pdata[j*city_num + i] -= mintime; if(pdata[i*city_num + j] == 0) tmpmark[j] = true; } } } } *time += mintime; memcpy(pmark, tmpmark, sizeof(bool) * city_num); for(i=0; i != city_num; ++i) //Check if all cities recieved the msg. if(!pmark[i]) return true; return false; } int main() { int city_num, *pdata, total_time = 0; bool mark[LIMIT] = {false}; // 1<= n <=100 scanf("%d", &city_num); pdata = (int*)malloc(sizeof(int) * city_num * city_num); memset(pdata, 0, sizeof(int) * city_num * city_num); get_data(city_num, pdata); mark[0] = true; while(spread(pdata, mark, city_num, &total_time)); printf("%d\n", total_time); return 0; } |
可能是错的，我也不知道……瞎搞