Scott's world.

哈利·波特的考试

Word count: 1.1kReading time: 5 min
2019/08/16 Share

图4 哈利·波特的考试

哈利·波特要考试了,他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha,将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念,例如ahah可以将老鼠变成猫。另外,如果想把猫变成鱼,可以通过念一个直接魔咒lalala,也可以将猫变老鼠、老鼠变鱼的魔咒连起来念:hahahehe。

现在哈利·波特的手里有一本教材,里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场,要考察他把这只动物变成任意一只指定动物的本事。于是他来问你:带什么动物去可以让最难变的那种动物(即该动物变为哈利·波特自己带去的动物所需要的魔咒最长)需要的魔咒最短?例如:如果只有猫、鼠、鱼,则显然哈利·波特应该带鼠去,因为鼠变成另外两种动物都只需要念4个字符;而如果带猫去,则至少需要念6个字符才能把猫变成鱼;同理,带鱼去也不是最好的选择。

输入格式:

输入说明:输入第1行给出两个正整数N (≤100)和M,其中N是考试涉及的动物总数,M是用于直接变形的魔咒条数。为简单起见,我们将动物按1~N编号。随后M行,每行给出了3个正整数,分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100),数字之间用空格分隔。

输出格式:

输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度,中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的,则输出0。如果有若干只动物都可以备选,则输出编号最小的那只。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
12
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80

输出样例:

1
4 70

题目分析

img

  • 这道题题目也就是典型的多源最短路径问题

所以我们也就要运用到多源最短路算法Floyd算法

代码分析

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
#include <math.h>
#define MaxV 100
#define MaxE 100
#define Max 100001
using namespace std;

typedef struct ENode *PtrToENode;
struct ENode{
int v1;
int v2;
int weight;
};
typedef PtrToENode Edge;


typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
int Data[MaxV][MaxV];
};
typedef PtrToGNode MGraph;


void FindAnimal(MGraph Graph);
int FindMaxDist(int D[][MaxV],int i,int N);
MGraph CreateGraph(int Nv);
MGraph BuildGraph();
MGraph BuildGraph();
void Floyd(MGraph Graph,int D[][MaxV]);
void InsertEdge(MGraph Graph,Edge E);

void FindAnimal(MGraph Graph)
{
int D[MaxV][MaxV],MaxDist,MinDist;
int Animal,i;

Floyd(Graph,D);

MinDist=Max;
for(i=0;i<Graph->Nv;i++)
{
MaxDist=FindMaxDist(D,i,Graph->Nv);
if(MaxDist==Max){
printf("0\n");
return ;
}
if(MinDist>MaxDist){
MinDist=MaxDist;
Animal=i+1;
}
}
printf("%d %d\n",Animal,MinDist);
}






int FindMaxDist(int D[][MaxV],int i,int N)
{
int MaxDist;
int j;

MaxDist=0;
for(j=0;j<N;j++)
if(i!=j&&MaxDist<D[i][j])
MaxDist=D[i][j];

return MaxDist;
}


MGraph CreateGraph(int Nv)
{
int V,W;
MGraph Graph;

Graph=(MGraph)malloc(sizeof(struct GNode));
Graph->Nv=Nv;
Graph->Ne=0;
for(V=0;V<Nv;V++)
for(W=0;W<Nv;W++)
Graph->Data[V][W]=Max;
return Graph;
}

MGraph BuildGraph()
{
MGraph Graph;
Edge E;
int Nv,i;

scanf("%d",&Nv);
Graph=CreateGraph(Nv);
scanf("%d",&(Graph->Ne));
if(Graph->Ne!=0){
E = (Edge)malloc(sizeof(struct ENode));
for(i=0;i<Graph->Ne;i++)
{
scanf("%d %d %d",&E->v1,&E->v2,&E->weight);
E->v1--;
E->v2--;
InsertEdge(Graph,E);
}
}
return Graph;
}

void InsertEdge(MGraph Graph,Edge E)
{
Graph->Data[E->v1][E->v2]=E->weight;
Graph->Data[E->v2][E->v1]=E->weight;
}


void Floyd(MGraph Graph,int D[][MaxV])
{
int i,j,k;

for(i=0;i<Graph->Nv;i++)
for(j=0;j<Graph->Nv;j++)
D[i][j]=Graph->Data[i][j];

for(k=0;k<Graph->Nv;k++)
for(i=0;i<Graph->Nv;i++)
for(j=0;j<Graph->Nv;j++)
if(D[i][k]+D[k][j] < D[i][j])
D[i][j] = D[i][k]+D[k][j];
}
int main()
{
MGraph G=BuildGraph();
FindAnimal(G);

return 0;
}
CATALOG
  1. 1. 图4 哈利·波特的考试
    1. 1.0.1. 输入格式:
    2. 1.0.2. 输出格式:
    3. 1.0.3. 输入样例:
    4. 1.0.4. 输出样例:
  2. 1.1. 题目分析
  3. 1.2. 代码分析