求解自行车慢速比赛问题。一个美丽的小岛上有许多景点,景点之间有一条或多条道路。现在进行自行车慢速比赛(最慢的选手获得冠军),工作人员在道路上标出自行车的单向行驶方向,所有比赛线路不会出现环,选手不能在中途的任何地方停下来,否则犯规,退出比赛。首先给定一行两个整数N和M,N为岛上的景点数(景点编号为0~N-1,N≤100),接下来的M行,每行为a、b、l,表示景点a和景点b之间的单向路径长度为l(l为整数)。最后一行为s和t,表示比赛的起点s和终点t。所有选手水平高超,都能够以自行车的最低速度行驶,并且所有自行车的最低速度相同。问冠军所走的路径长度是多少?(C语言)
时间: 2024-02-12 22:04:41 浏览: 91
自行车比赛
这是一个求解最长路径的问题,可以使用拓扑排序和动态规划来解决。
首先进行拓扑排序,将所有景点按照拓扑序列从小到大排序。接着,对于每个景点i,从起点s到i的最长路径长度为:
max{d[j]+l[j][i]},其中j是i的前驱节点,l[j][i]是从j到i的路径长度,d[j]是从起点s到j的最长路径长度。
最后,从终点t到起点s逆推,得到冠军所走的路径长度。
以下是C语言代码实现:
```c
#include <stdio.h>
#include <string.h>
#define MAXN 100
#define INF 0x3f3f3f3f
int n, m, s, t;
int g[MAXN][MAXN], d[MAXN], topo[MAXN], in[MAXN];
void topsort() {
int q[MAXN], t = -1;
for (int i = 0; i < n; i++) {
if (in[i] == 0) {
q[++t] = i;
}
}
int cnt = 0;
while (t >= 0) {
int u = q[t--];
topo[cnt++] = u;
for (int v = 0; v < n; v++) {
if (g[u][v] != INF) {
in[v]--;
if (in[v] == 0) {
q[++t] = v;
}
}
}
}
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
memset(g, 0x3f, sizeof(g));
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u][v] = w;
in[v]++;
}
topsort();
memset(d, 0xcf, sizeof(d));
d[s] = 0;
for (int i = 0; i < n; i++) {
int u = topo[i];
for (int v = 0; v < n; v++) {
if (g[u][v] != INF) {
if (d[u] + g[u][v] > d[v]) {
d[v] = d[u] + g[u][v];
}
}
}
}
printf("%d\n", d[t]);
return 0;
}
```
阅读全文