UVA 567 – Risk

跳到分析跳到代码

题目大意： 给出一个无向图（可以有环），要求从指定起点到指定终点的最短距离。

题目的输入输出很恶心，下面给出sample：

Sample Input 1

13//i=1，1-th行，指序号为 i 的点跟 哪些大于i 的点相邻， 第一个数X指 后面有X个数。

23 4

3 4 5 6

1 6

1 7

2 12 13

1 8

2 9 10

1 11

1 11

2 12 17

1 14

2 14 15

2 15 16

1 16

1 19

2 18 19

1 20

120//i = 19，19-th行。

5//20-th行，N表示下面有几组(起点，终点)。

1 20 //第一组

2 9

19 5

18 19

16 20 //第五组

Sample Output 2

Test Set #1 //格式 第 T 组数据

1 to 20:7//从哪个点 到 哪个 点，最小路径多长。（长度算终点，不算起点）

2 to 9:5

19 to 5: 6

18 to 19: 2

16 to 20: 2

//每组数据间留空行

Test Set #2

1 to 20: 4

8 to 20: 5

15 to 16: 2

11 to 4: 1

7 to 13: 3

2 to 16: 4

题目类型：

分析：

代码：

①

// Accepted C++ 0.104 2011-04-07 04:19:03 //20个点的无权无向图 bfs #include<cstdio> #include<cstring> #include<vector> #include<queue> //不要求输出路径 using namespace std; #define MAXN 22 vector<int> G[MAXN]; //固定20 个点 / 1~20 queue<int> q; int vis[MAXN]; int pa[MAXN]; int st, en; int ans; void clear_queue() { while(!q.empty()) q.pop(); } void bfs() { clear_queue(); //!! q.push(st); while(!q.empty()) { int u = q.front(); q.pop(); for(int i=0; i<(int)G[u].size(); i++) { int v = G[u][i]; if(vis[v]) continue; pa[v] = u; if(v == en) return; //找到 q.push(v); vis[v] = 1; //每个点最多只能入队一次 } } } int dist() { int u = en; for(int i=0; ; i++) { if(u == st) return i; //!dist u = pa[u]; } } void clear_graph() { for(int i=1; i<=20; i++) //20个点 if(!G[i].empty()) G[i].clear(); } int read_graph() { clear_graph(); int ok=1; for(int i=1; i<=19; i++) { int u = i; int v, n; if(scanf("%d", &n) == EOF) {ok = 0; break; } for(int i=0; i<n; i++) { scanf("%d", &v); G[u].push_back(v); G[v].push_back(u); } } if(ok) return 1; else return 0; } int main() { int T=1; while(read_graph()) { printf("Test Set #%d/n", T++); int n; //几组 起点 终点 scanf("%d", &n); for(int i=0; i<n; i++) { memset(vis, 0, sizeof(vis)); scanf("%d%d", &st, &en); bfs(); printf("%2d to %2d: %d/n", st, en, dist()); //右对齐 } printf("/n"); //每组数据后换行 } }

②

//Accepted C++ 0.084 2011-04-07 04:22:43 //比STLqueue快一些 //=============================== #include<cstdio> #include<cstring> #include<vector> using namespace std; #define MAXN 22 //最大20个点 vector<int> G[MAXN]; //1~20 int q[MAXN]; int front, rear; int st, en; //起点 终点 //int pa[MAXN]; int d[MAXN]; int vis[MAXN]; void bfs() //int ???tot?? { int tot = 0; front = rear = 0; q[rear++] = st; //q是不用清的，每次都会刷新，还有下标控制 vis[st] = 1; d[st]=0; while(front < rear) //当非空 { int u = q[front++]; //if(u == en) { tot++; return tot; } //for(int i=0; i<G[u].size(); i++) if(!vis[G[u][i]] && G[u][i] != pa[u] && (u == st || pa[u] != pa[G[u][i]])) //还应该让它不要去搜同层的！ //for(int i=0; i<(int)G[u].size(); i++) if(!vis[G[u][i]] && G[u][i] != pa[u]) for(int i=0; i<(int)G[u].size(); i++) if(!vis[G[u][i]]) //先令vis[st] = 1了，就可以不要判断G[u][i] != pa[u] { int v = G[u][i]; //if(v == en) { tot++; return tot; } //if(!pa[v]) pa[v] = u; // //pa[v] = u; // d[v]=d[u]+1; //指标 if(v == en) return; // vis[v] = 1; q[rear++] = v; } } } /* //无需打印路径 int ans(int cur) //可以用pa放路长，相当于指标d了 { int tot=0; while(pa[cur]) { tot++; cur = pa[cur]; } return tot; } */ int input() { int ok=0; for(int i=1; i<=19; i++) { int x; if(!ok && scanf("%d", &x)!=EOF) ok=1; // else if(!ok) return 0; else scanf("%d", &x); // for(int j=0; j<x; j++) { int t; scanf("%d", &t); G[i].push_back(t); G[t].push_back(i); } } //前19行输入完毕 return 1; } void clear() { //for(int i=1; i<=19; i++) //!错误之处 for(int i=1; i<=20; i++) //!错误之处 G[20]也要清空 if(!G[i].empty()) G[i].clear(); } int main() { int T=1; while(input()) { //if(T != 1)printf("/n"); //最后一例有没有空行？ printf("Test Set #%d/n", T++); int n; //n组起点终点 scanf("%d", &n); for(int i=0; i<n; i++) { memset(vis, 0, sizeof(vis)); //memset(pa, 0, sizeof(pa)); //不依靠pa判断 scanf("%d%d", &st, &en); bfs(); //printf("%d/n", d[en]); printf("%2d to %2d: %d/n", st, en, d[en]); //printf("%d/n", ans(en)); } printf("/n"); clear(); } }

原文链接: https://www.cnblogs.com/tclh123/archive/2011/03/30/2587115.html

**欢迎关注**

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍