Skip to content

狗子窝

没事就吠一下

Menu
  • 首页
  • 技术交流
    • 原创
    • WebGL教程
    • js小程序在线演示
    • 摘要总结
  • 小评论
    • 动漫短评
    • 其他短评
  • 日志/心情
    • My Piano
    • 絮絮叨叨
    • 长篇大论
  • 关于我
    • 留言板
Menu

无聊发一题。

Posted on 2013 年 5 月 5 日2013 年 5 月 5 日 by wysaid

无聊发一题。

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

不知道做对没
C
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;
}

 

1 thought on “无聊发一题。”

  1. wysaid说道:
    2013 年 5 月 5 日 下午 5:26

    可能是错的,我也不知道……瞎搞

Comments are closed.


转载本Blog文章请注明出处:
wysaid.org

2025 年 5 月
日 一 二 三 四 五 六
 123
45678910
11121314151617
18192021222324
25262728293031
« 2 月    

评论

  • 翔鱼 发表在《关于我》
  • luo.la 发表在《使用OpenAL打开麦克风录音并实时回放(类似K歌效果)》
  • 罗拉 发表在《使用OpenAL打开麦克风录音并实时回放(类似K歌效果)》
  • 大喜 发表在《使用OpenAL打开麦克风录音并实时回放(类似K歌效果)》
  • 罗拉套图网 发表在《使用OpenAL打开麦克风录音并实时回放(类似K歌效果)》

归档

分类

TAG

Android c C++ domain EGE host iOS JavaScript NDK OpenAL OpenGL Slideshow WebGL教程 WGE 人脸识别 作文 分形 动漫 在线演示 小程序 常识 数学 游戏 源代码 滤镜 算法 老文翻新 表白 视频 评论 谷歌娘 酸腐文章 钢琴 音乐
© 2025 狗子窝 | Powered by Superbs Personal Blog theme