Skip to content

大师兄的博客

专注无聊20年,数过的小羊连起来可以绕地球两圈

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

2023年 3月
日 一 二 三 四 五 六
 1234
567891011
12131415161718
19202122232425
262728293031  
« 7月    

评论

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

归档

分类

TAG

Android c C++ domain EGE host iOS JavaScript NDK OpenAL OpenGL Slideshow WebGL教程 WGE 人脸识别 分形 动漫 在线演示 小程序 常识 数学 游戏 源代码 滤镜 算法 表白 视频 评论 谷歌娘 钢琴 音乐
© 2023 大师兄的博客 | Powered by Superbs Personal Blog theme