万字长文，整理不易。点赞加评论期末高分过！
感谢你这么帅（漂亮）还支持我
7-8 最短工期
一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。
输入格式：
首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。
输出格式：
如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。
输入样例 1：
9 12 0 1 6 0 2 4 0 3 5 1 4 1 2 4 1 3 5 2 5 4 0 4 6 9 4 7 7 5 7 4 6 8 2 7 8 4
输出样例 1：
18
输入样例 2：
4 5 0 1 1 0 2 2 2 1 3 1 3 4 3 2 5
解析
#include <stdio.h> #include <stdlib.h> #include <string.h> int n, m, ans; int mp[100][100]; int l[100], q[100], t[100]; int main() { int a, b, c, head = 0, tail = 0; scanf("%d%d", &n, &m); memset(mp, -1, sizeof(mp)); for (int i = 0; i < m; i++) { scanf("%d%d%d", &a, &b, &c); mp[a][b] = c; l[b]++; } for (int i = 0; i < n; i++) { if (!l[i]) { q[tail++] = i; } } while (head < tail) { int temp = q[head++]; if (t[temp] > ans) ans = t[temp]; for (int i = 0; i < n; i++) { if (mp[temp][i] != -1) { l[i]--; if (!l[i]) q[tail++] = i; if (t[i] < t[temp] + mp[temp][i]) { t[i] = t[temp] + mp[temp][i]; } } } } if (tail < n) printf("Impossible"); else printf("%d", ans); }
7-9 哈利·波特的考试
哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。
现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。
输入格式:
输入说明：输入第1行给出两个正整数N (≤100)和M，其中N是考试涉及的动物总数，M是用于直接变形的魔咒条数。为简单起见，我们将动物按1~N编号。随后M行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(≤100)，数字之间用空格分隔。
输出格式:
输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。
输入样例:
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
输出样例:
4 70
解析
/** * 7-9 哈利·波特的考试 * 最短路径 迪杰斯特拉算法 */ #include<stdio.h> #include<string.h> #define maxInt 2147483647 typedef struct { int arcs[102][102]; int vexnum, arcnum; } MGraph; int final[102];//final[w]=1表示求得顶点v0至vw的最短路径 int D[102]; //记录v0到vi的当前最短路径长度 int P[102]; //记录v0到vi的当前最短路径vi的前驱 int i, u, j, m, v, min, w, k, a, b, c, min1 = 999999, max = -991111, p = 0; void Dijkstra(MGraph G, int v0) { for (v = 0; v < G.vexnum; v++) //初始化数据 { final[v] = 0; //全部顶点初始化为未知最短路径状态 D[v] = G.arcs[v0][v];// 将与v0点有连线的顶点加上权值 P[v] = -1; //初始化路径数组P为-1 } D[v0] = 0; //v0至v0路径为0 final[v0] = 1; // v0至v0不需要求路径 // 开始主循环，每次求得v0到某个v顶点的最短路径 for (v = 1; v < G.vexnum; v++) { min = maxInt; // 当前所知离v0顶点的最近距离 for (w = 0; w < G.vexnum; w++) // 寻找离v0最近的顶点 { if (!final[w] && D[w] < min) { k = w; min = D[w]; // w顶点离v0顶点更近 } } final[k] = 1; // 将目前找到的最近的顶点置为1 for (w = 0; w < G.vexnum; w++) // 修正当前最短路径及距离 { // 如果经过v顶点的路径比现在这条路径的长度短的话 if (!final[w] && (min + G.arcs[k][w] < D[w])) { // 说明找到了更短的路径，修改D[w]和P[w] D[w] = min + G.arcs[k][w]; // 修改当前路径长度 P[w] = k; } } } } int main() { MGraph G; memset(final, 0, sizeof(final)); memset(D, 0x3f3f3f3f, sizeof(D)); memset(G.arcs, 0x3f3f3f3f, sizeof(G.arcs)); //邻接矩阵一定要初始化 scanf("%d %d", &G.vexnum, &m); for (i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &c); G.arcs[a - 1][b - 1] = c; G.arcs[b - 1][a - 1] = c; } for (u = 0; u < G.vexnum; u++) { max = -9999999; Dijkstra(G, u); for (j = 0; j < G.vexnum; j++) { if (D[j] > max) max = D[j]; } if (max < min1) { min1 = max; p = u + 1; } } if (p == 0) printf("0"); else printf("%d %d\n", p, min1); return 0; }
7-10 旅游规划
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20
输出样例:.
3 40
解析
#include <stdio.h> #include <stdbool.h> #define MAX_SIZE 500 #define INF 1000000 typedef struct { int city; int length; int fee; } Road; int dijkstra(Road graph[MAX_SIZE][MAX_SIZE], int N, int S, int D, int *path) { bool visited[MAX_SIZE] = {false}; int distances[MAX_SIZE]; int fees[MAX_SIZE]; for (int i = 0; i < N; i++) { distances[i] = INF; fees[i] = INF; path[i] = -1; } distances[S] = 0; fees[S] = 0; for (int count = 0; count < N - 1; count++) { int minDist = INF; int minCity = -1; // 找到当前距离最小的城市 for (int i = 0; i < N; i++) { if (!visited[i] && distances[i] < minDist) { minDist = distances[i]; minCity = i; } } visited[minCity] = true; // 更新相邻城市的距离和费用 for (int i = 0; i < N; i++) { if (!visited[i] && graph[minCity][i].city != -1) { int newDist = distances[minCity] + graph[minCity][i].length; int newFee = fees[minCity] + graph[minCity][i].fee; if (newDist < distances[i] || (newDist == distances[i] && newFee < fees[i])) { distances[i] = newDist; fees[i] = newFee; path[i] = minCity; } } } } return distances[D]; } int main() { int N, M, S, D; scanf("%d %d %d %d", &N, &M, &S, &D); Road graph[MAX_SIZE][MAX_SIZE]; for (int i = 0; i < MAX_SIZE; i++) { for (int j = 0; j < MAX_SIZE; j++) { graph[i][j].city = -1; graph[i][j].length = -1; graph[i][j].fee = -1; } } for (int i = 0; i < M; i++) { int city1, city2, length, fee; scanf("%d %d %d %d", &city1, &city2, &length, &fee); graph[city1][city2].city = city2; graph[city1][city2].length = length; graph[city1][city2].fee = fee; graph[city2][city1].city = city1; graph[city2][city1].length = length; graph[city2][city1].fee = fee; } int path[MAX_SIZE]; int shortestDistance = dijkstra(graph, N, S, D, path); int totalFee = 0; // 计算路径的总费用 int city = D; while (path[city] != -1) { totalFee += graph[city][path[city]].fee; city = path[city]; } printf("%d %d\n", shortestDistance, totalFee); return 0; }
