水题笔记_最优乘车 [(真正的水题)想咋做咋做]

最近他们学图论…做拓扑排序到心态爆炸…

不过修好了vs2017 以及发现了win10的一些黑科技….
onenote真他娘好用QAQ

懵逼的 题目

最优乘车
[问题描述]
H城是一个旅游胜地,每年都有成千上万的人前来观光。为方便游客,巴士公司在各个旅游景点及宾馆,饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发,依次途经若干个巴士站,最终到达终点巴士站。
一名旅客最近到H城旅游,他很想去S公园游玩,但如果从他所在的饭店没有一路巴士可以直接到达S公园,则他可能要先乘某一路巴士坐几站,再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。
现在用整数1,2,…N 给H城的所有的巴士站编号,约定这名旅客所在饭店的巴士站编号为1,S公园巴士站的编号为N。
写一个程序,帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程
中换车的次数最少。
[输入格式]
输入文件是Travel.in。文件的第一行有两个数字M和N(1<=M<=100 1<=N<=500),表示开通了M条单程巴士线路,总共有N个车站。从第二行到第M刊行依次给出了第1条到第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息,从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。
[输出格式]
输出文件是Travel.out,文件只有一行。如果无法乘巴士从饭店到达S公园,则输出”NO”,否则输出你的程序所找到的最少换车次数,换车次数为0表示不需换车即可到达。
[输入样例]
Travel.in

1
2
3
4
5

3 7
6 7
4 7 3 6
2 1 3 5

[输出样例]
Travel.out

1
2

扯淡的 题解

你就不能走路嘛你就不能走路嘛你就不能走路嘛(划掉)
思路还是挺简单的…就是在每一条路线上给前面的点到后面的点连边(有向的, 边权为1)然后跑最短路…权当复习spfa(好像bfs就口以)了…就是输入可蒸鹅心…(我有一句mmp现在就要讲)
因为不管从哪个点到哪个点 只要在一条线路上,都算是乘了一次车,跑最短路的结果就是乘车的总次数…把最短路减1就是换乘的次数咯…

SAN == 0 的 程序

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
// travel.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <queue>
#define INF (0x7fffffff)
#define MAXN (500 + 5)
#define MAXM (100 + 5)
using namespace std;
struct edg
{
int next;
int to;
}b[MAXM * MAXN * 2];
int cntm = 0;
int n;
int m;
int g[MAXN];
char sr[MAXM][MAXN * MAXM * 30];
int sri[MAXN][MAXN * MAXM * 2];
void zhuan();//把字符串转化为整数数组的...
void adn(int, int);//往邻接表里加边的...
int main()
{
cin >> m >> n;
for (int i = 0; i <= m; i++)
{
cin.getline(sr[i], (MAXN * MAXM), '\n');
}
zhuan();
/*for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= sri[i][0]; j++)
{
cout << sri[i][j] << " ";
}
puts("");
}*/
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= sri[i][0]; j++)
{
for (int k = 1; k < j; k++)
{
adn(sri[i][k], sri[i][j]);
}
}
}
/*for (int i = 1; i <= n; i++)
{
for (int j = g[i]; j != 0; j = b[j].next)
{
printf("%d ", b[j].to);
}
puts("");
}*/
queue<int> q;
q.push(1);
int d[MAXN];
bool v[MAXN];
int dq;
memset(v, false, sizeof(v));
for (int i = 1; i <= n; i++)
{
d[i] = INF;
}
d[1] = 0;
while (!q.empty())
{
dq = q.front();
v[dq] = false;
q.pop();
for (int i = g[dq]; i != 0; i = b[i].next)
{
if (d[b[i].to] > (d[dq] + 1))
{
d[b[i].to] = d[dq] + 1;
if (!v[b[i].to])
{
q.push(b[i].to);
v[b[i].to] = true;
}
}
}
}
/*for (int i = 1; i <= n; i++)
{
printf("%d ", d[i]);
}*/
if (d[n] != INF)
{
cout << d[n] - 1;
}
else
{
puts("NO");
}
return 0;
}
void adn(int f, int t)
{
b[++cntm].next = g[f];
b[cntm].to = t;
g[f] = cntm;
}
void zhuan()
{
for (int i = 1; i <= m; i++)
{
int xn = strlen(sr[i]);
int re = 0;
for (int j = 0; j < xn; j++)
{
while (sr[i][j] < '0' || sr[i][j] > '9')
{
j++;
}
while (sr[i][j] <= '9' && sr[i][j] >= '0')
{
re *= 10;
re += (sr[i][j] - '0');
j++;
}
sri[i][++sri[i][0]] = re;
re = 0;
}
}
}
/*
3 7
6 7
4 7 3 6
2 1 3 5
*/

By SAN == 0 的 Cansult

啊哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈(此人已疯)