Week7图（中）
7.1 最短路径问题
最短路径问题的抽象
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径
- 这条路径就是两点之间的最短路径（ShortestPath）
- 第一个顶点为源点（Source）
- 最后一个顶点为终点（Destination）
问题分类
单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
- （有向）无权图
- （有向）有权图
多源最短路径问题：求任意两顶点间的最短路径。
无权图的单源最短路算法
按照递增（非递减） 的顺序找出到各个顶点的最短路
BFS!
void Unweighted(Vertex S) {
Enqueue(S, Q);
while (!IsEmpty(Q)) {
V = Dequeue(Q);
for (V 的每个邻接点 W)
if (dist[W] == -1) {
dist[W] = dist[V] + 1;
path[W] = V;
Enqueue(W, Q);
}
}
}
/*
dist[W] = S到W的最短距离
dist[S] = 0
path[W] = S到W的路上经过的某顶
*/有权图的单源最短路算法
按照递增的顺序找出到各个顶点的最短路
Dijkstra 算法
令$S$={源点$s$ + 已经确定了最短路径的顶点$v_i$}
对任一未收录的顶点$v$，定义$dist[v]$为s到v的最短路径长度，但该路径仅经过S中的顶点。即路径
{$s\rightarrow(vi\in S)\rightarrow v$}的最小长度
若路径是按照递增（非递减） 的顺序生成的，则
- 真正的最短路必须只经过S中的顶点（为什么？）
- 反证:假设最短路经过$w($不属于S$)，s\rightarrow w \rightarrow v $为最短路，则$s\rightarrow w$比$s\rightarrow v$要短，而$v$是下一个马上要收进去的顶点（真正的最短路），与之矛盾！
- 每次从未收录的顶点中选一个$dist$最小的收录（贪心）
- 增加一个$v$进入$S$，可能影响另外一个$w$的$dist$值！（只影响邻接点）
$dist[w] = min${$dist[w], dist[v] + <v,w>$ 的权重}
注意负值圈！
void Dijkstra(Vertex s) {
while (1) {
V = 未收录顶点中dist最小者;
if (这样的V不存在)
break;
collected[V] = true;
for (V 的每个邻接点 W)
if (collected[W] == false)
if (dist[V] + E<V, W> < dist[W]) {
dist[W] = dist[V] + E<V, W>;
path[W] = V;
}
}
} /* 不能解决有负边的情况 */找未收录顶点中dist最小者方法
方法1：直接扫描所有未收录顶点 $—— O( |V| )$
对稠密图效果较好
$T = O( |V|^2 + |E| )$
方法2：将$dist$存在最小堆中 $ ——O( log|V| )$
对稀疏图效果较好
更新$dist[w]$的值 $—— O( log|V| )$
$T = O( |V| log|V| + |E| log|V| ) = O( |E| log|V| )$
多源最短路算法
方法1：直接将单源最短路算法调用$|V|$遍
对稠密图效果较好
$T = O( |V|^3 + |E|\times|V|)$
方法2：Floyd算法
对于稀疏图效果好
$T = O( |V|^3 )$
Floyd 算法
$D^k[i][j] =$ 路径$\{ i \rightarrow \{ l \leq k \} \rightarrow j \}$的最小长度
$D^0, D^1, …, D^{|V|-1}[i][j]$即给出了$i$到$j$的真正最短距离
最初的$D^{-1}$是开始的邻接矩阵
当$D^{k-1}$已经完成，递推到$D^k$时：
或者$k \notin$最短路径$\{ i \rightarrow \{ l\leq k \} \rightarrow j \}$，则$D^k = D^{k-1}$
或者$k \in$ 最短路径$\{ i \rightarrow \{ l \leq k \} \rightarrow j \}$，则该路径必定由两段最短路径组成:$D^k[i][j]=D^{k-1}[i][k]+D^{k-1}[k][j] $
细节上，邻接矩阵无边处打成无穷。
void Floyd() {
for (i = 0; i < N; i++)
for (j = 0; j < N; j++) {
D[i][j] = G[i][j];
path[i][j] = -1;
}
for (k = 0; k < N; k++)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (D[i][k] + D[k][j] < D[i][j]) {
D[][j] = [i][k] + D[k][j];
path[i][j] = k;
}
}代码模板
/* 邻接表存储 - 无权图的单源最短路算法 */
/* dist[]和path[]全部初始化为-1 */
void Unweighted(LGraph Graph, int dist[], int path[], Vertex S) {
Queue Q;
Vertex V;
PtrToAdjVNode W;
Q = CreateQueue(Graph->Nv); /* 创建空队列, MaxSize为外部定义的常数 */
dist[S] = 0; /* 初始化源点 */
AddQ(Q, S);
while (!IsEmpty(Q)) {
V = DeleteQ(Q);
for (W = Graph->G[V].FirstEdge; W;
W = W->Next) /* 对V的每个邻接点W->AdjV */
if (dist[W->AdjV] == -1) { /* 若W->AdjV未被访问过 */
dist[W->AdjV] = dist[V] + 1; /* W->AdjV到S的距离更新 */
path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
AddQ(Q, W->AdjV);
}
} /* while结束*/
}
Vertex FindMinDist(MGraph Graph,
int dist[],
int collected[]) { /* 返回未被收录顶点中dist最小者 */
Vertex MinV, V;
int MinDist = INFINITY;
for (V = 0; V < Graph->Nv; V++) {
if (collected[V] == false && dist[V] < MinDist) {
/* 若V未被收录，且dist[V]更小 */
MinDist = dist[V]; /* 更新最小距离 */
MinV = V; /* 更新对应顶点 */
}
}
if (MinDist < INFINITY) /* 若找到最小dist */
return MinV; /* 返回对应的顶点下标 */
else
return ERROR; /* 若这样的顶点不存在，返回错误标记 */
}
bool Dijkstra(MGraph Graph, int dist[], int path[], Vertex S) {
int collected[MaxVertexNum];
Vertex V, W;
/* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */
for (V = 0; V < Graph->Nv; V++) {
dist[V] = Graph->G[S][V];
if (dist[V] < INFINITY)
path[V] = S;
else
path[V] = -1;
collected[V] = false;
}
/* 先将起点收入集合 */
dist[S] = 0;
collected[S] = true;
while (1) {
/* V = 未被收录顶点中dist最小者 */
V = FindMinDist(Graph, dist, collected);
if (V == ERROR) /* 若这样的V不存在 */
break; /* 算法结束 */
collected[V] = true; /* 收录V */
for (W = 0; W < Graph->Nv; W++) /* 对图中的每个顶点W */
/* 若W是V的邻接点并且未被收录 */
if (collected[W] == false && Graph->G[V][W] < INFINITY) {
if (Graph->G[V][W] < 0) /* 若有负边 */
return false; /* 不能正确解决，返回错误标记 */
/* 若收录V使得dist[W]变小 */
if (dist[V] + Graph->G[V][W] < dist[W]) {
dist[W] = dist[V] + Graph->G[V][W]; /* 更新dist[W] */
path[W] = V; /* 更新S到W的路径 */
}
}
} /* while结束*/
return true; /* 算法执行完毕，返回正确标记 */
}
/* 邻接矩阵存储 - 多源最短路算法 */
bool Floyd(MGraph Graph,
WeightType D[][MaxVertexNum],
Vertex path[][MaxVertexNum]) {
Vertex i, j, k;
/* 初始化 */
for (i = 0; i < Graph->Nv; i++)
for (j = 0; j < Graph->Nv; j++) {
D[i][j] = Graph->G[i][j];
path[i][j] = -1;
}
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];
if (i == j && D[i][j] < 0) /* 若发现负值圈 */
return false; /* 不能正确解决，返回错误标记 */
path[i][j] = k;
}
return true; /* 算法执行完毕，返回正确标记 */
}编程习题
1.哈利·波特的考试
哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是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思路
一句话概括本题就是多源最短路径问题，利用Floyd算法即可（邻接矩阵存储）。
AC code
#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100 /* 最大顶点数设为100 */
#define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex; /* 用顶点下标表示顶点,为整型 */
typedef int WeightType; /* 边的权值设为整型 */
/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode {
Vertex V1, V2; /* 有向边<V1, V2> */
WeightType Weight; /* 权重 */
};
typedef PtrToENode Edge;
/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; /* 顶点数 */
int Ne; /* 边数 */
WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
MGraph CreateGraph(int VertexNum) {
/* 初始化一个有VertexNum个顶点但没有边的图 */
Vertex V, W;
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
Graph->Nv = VertexNum;
Graph->Ne = 0;
/* 初始化邻接矩阵 */
/* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
for (V = 0; V < Graph->Nv; V++)
for (W = 0; W < Graph->Nv; W++) Graph->G[V][W] = INFINITY;
return Graph;
}
void InsertEdge(MGraph Graph, Edge E) {
/* 插入边 <V1, V2> */
Graph->G[E->V1][E->V2] = E->Weight;
/* 若是无向图，还要插入边<V2, V1> */
Graph->G[E->V2][E->V1] = E->Weight;
}
MGraph BuildGraph() {
MGraph Graph;
Edge E;
int Nv, i;
scanf("%d", &Nv); /* 读入顶点个数 */
Graph = CreateGraph(Nv); /* 初始化有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--; /*编号从0开始*/
InsertEdge(Graph, E);
}
}
return Graph;
}
void Floyd(MGraph Graph, WeightType D[][MaxVertexNum]) {
Vertex i, j, k;
/* 初始化 */
for (i = 0; i < Graph->Nv; i++)
for (j = 0; j < Graph->Nv; j++) D[i][j] = Graph->G[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] && i != j)
D[i][j] = D[i][k] + D[k][j];
}
WeightType FindMaxDist(WeightType D[][MaxVertexNum], Vertex i, int N) {
WeightType MaxDist;
Vertex j;
MaxDist = 0;
for (j = 0; j < N; j++) /* 找出i到其他动物j的最长距离 */
if (i != j && D[i][j] > MaxDist) MaxDist = D[i][j];
return MaxDist;
}
void FindAnimal(MGraph Graph) {
WeightType D[MaxVertexNum][MaxVertexNum], MaxDist, MinDist;
Vertex Animal, i;
Floyd(Graph, D);
MinDist = INFINITY;
for (i = 0; i < Graph->Nv; i++) {
MaxDist = FindMaxDist(D, i, Graph->Nv);
if (MaxDist == INFINITY) { /* 说明有从i无法变出的动物 */
printf("0\n");
return;
}
if (MinDist > MaxDist) { /* 找到最长距离更小的动物 */
MinDist = MaxDist;
Animal = i + 1; /* 更新距离，记录编号 */
}
}
printf("%d %d\n", Animal, MinDist);
}
int main() {
MGraph G = BuildGraph();
FindAnimal(G);
return 0;
}| 测试点 | 提示 | 结果 | 分数 | 耗时 | 内存 |
|---|---|---|---|---|---|
| 0 | sample换数字，只有唯一解 | 答案正确 | 12 | 4 ms | 296 KB |
| 1 | 无解 | 答案正确 | 1 | 4 ms | 188 KB |
| 2 | 最大N的等边长环，解不唯一，输出最小编号 | 答案正确 | 4 | 6 ms | 308 KB |
| 3 | 最大N，最大M，随机完全图 | 答案正确 | 8 | 9 ms | 300 KB |
2.Saving James Bond - Hard Version
This time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape – he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).
Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at $(0,0)$ and the northeast corner at$ (50,50)$. The central island is a disk centered at$(0,0)$ with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.
Input Specification:
Each input file contains one test case. Each case starts with a line containing two positive integers $N (≤100)$, the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the $(x,y)$ location of a crocodile. Note that no two crocodiles are staying at the same position.
Output Specification:
For each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position$ (x,y)$ of each crocodile on the path, each pair in one line, from the island to the bank. If it is impossible for James to escape that way, simply give him 0 as the number of jumps. If there are many shortest paths, just output the one with the minimum first jump, which is guaranteed to be unique.
Sample Input 1:
17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10Sample Output 1:
4
0 11
10 21
10 35Sample Input 2:
4 13
-12 12
12 12
-12 -12
12 -12Sample Output 2:
0思路
好人做到底，如果能跳出，输出需要几跳以及鳄鱼坐标。这题必须用BFS！同时看测试点的提示会发现坑点不少！需要组织好逻辑。
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1001
#define ERROR -1
typedef int ElementType;
typedef int Position;
struct QNode {
ElementType *Data; /* 存储元素的数组 */
Position Front, Rear; /* 队列的头、尾指针 */
int MaxSize; /* 队列最大容量 */
};
typedef struct QNode *Queue;
Queue CreateQueue(int MaxSize) {
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
Q->Front = Q->Rear = 0;
Q->MaxSize = MaxSize;
return Q;
}
int AddQ(Queue Q, ElementType X) {
Q->Rear = (Q->Rear + 1);
Q->Data[Q->Rear] = X;
return 1;
}
int IsEmpty(Queue Q) { return (Q->Front == Q->Rear); }
ElementType DeleteQ(Queue Q) {
Q->Front = (Q->Front + 1);
return Q->Data[Q->Front];
}
int D; // 跳跃距离
const double first_D = 15;
int ans = 0, index[20], Stack[20], pre[20], ans_jump = 65536;
#define MaxVertexNum 100 /* 最大顶点数设为100 */
/* 图结点的定义 */
struct Node {
int x, y, first, visit, safe;
};
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; /* 顶点数 */
struct Node G[MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
// 距离
int Distance(int x1, int y1, int x2, int y2) {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
//能否到岸边
int Is_shore(int x, int y) {
// 分别计算当前结点与岸边的距离
// 即与 (x,50),(x,-50),(50,y),(-50,y) 的距离
if (abs(x - 50) <= D || abs(x + 50) <= D || abs(y + 50) <= D ||
abs(y - 50) <= D)
return 1;
return 0;
}
//是否安全("能上岸")
void Init_Safe(MGraph Graph) {
for (int i = 0; i < Graph->Nv; i++) {
// 如果该鳄鱼能到岸边
if (Is_shore(Graph->G[i].x, Graph->G[i].y))
Graph->G[i].safe = 1;
else
Graph->G[i].safe = 0;
}
}
//可以第一步跳上去
void Init_first(MGraph Graph) {
for (int i = 0; i < Graph->Nv; i++) {
// 如果该鳄鱼位置和"湖中心"相邻（跳跃距离+半径）
if (Distance(Graph->G[i].x, Graph->G[i].y, 0, 0) <=
(D + first_D / 2) * (D + first_D / 2) &&
Distance(Graph->G[i].x, Graph->G[i].y, 0, 0) >
first_D * first_D / 4)
Graph->G[i].first = 1;
else
Graph->G[i].first = 0;
}
}
MGraph BuildGraph() {
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
scanf("%d", &Graph->Nv); /* 读入顶点个数 */
scanf("%d", &D); /* 读入直径 */
for (int i = 0; i < Graph->Nv; i++) {
scanf("%d %d", &Graph->G[i].x, &Graph->G[i].y);
Graph->G[i].visit = 0;
}
Init_Safe(Graph);
Init_first(Graph);
return Graph;
}
void BFS(MGraph Graph, int v) {
Queue Q;
int cnt = 1, V, W, last = v, tail, first;
Q = CreateQueue(MAXSIZE); /* 创建空队列, MaxSize为外部定义的常数 */
Graph->G[v].visit = 1;
first = v;
pre[v] = -1;
AddQ(Q, v);
while (!IsEmpty(Q)) {
V = DeleteQ(Q); /* 弹出V */
for (W = 0; W < Graph->Nv; W++) { // 未跳过，且能跳上
if (!Graph->G[W].visit &&
Distance(Graph->G[V].x, Graph->G[V].y, Graph->G[W].x,
Graph->G[W].y) <= D * D) {
Graph->G[W].visit = 1;
AddQ(Q, W);
pre[W] = V;
tail = W;
if (Graph->G[W].safe) {
ans = 1;
if (cnt < ans_jump ||
cnt == ans_jump &&
(Distance(Graph->G[first].x, Graph->G[first].y, 0, 0) <
Distance(Graph->G[index[0]].x,Graph->G[index[0]].y, 0, 0))) {
int cnt1 = 0, cnt2 = 0;
while (W != -1) {
Stack[cnt1++] = W;
W = pre[W];
}
while (cnt1) index[cnt2++] = Stack[--cnt1];
ans_jump = cnt;
}
return;
}
}
}
if (V == last) {
++cnt;
last = tail;
}
}
}
void Save007(MGraph Graph) {
if (Is_shore(0, 0)) {
printf("1");
return;
}
for (int v = 0; v < Graph->Nv; v++)
if (Graph->G[v].first) {
for (int w = 0; w < Graph->Nv; w++) Graph->G[w].visit = 0;
BFS(Graph, v);
}
if (ans) {
printf("%d\n", ans_jump + 2);
for (int i = 0; i < ans_jump + 1; ++i)
printf("%d %d\n", Graph->G[index[i]].x, Graph>G[index[i]].y);
} else
printf("0");
}
int main() {
MGraph Graph = BuildGraph();
Save007(Graph);
return 0;
}| 测试点 | 提示 | 结果 | 分数 | 耗时 | 内存 |
|---|---|---|---|---|---|
| 0 | sample1 多条最短路，同一点有多路，最近点无路，多连通 | 答案正确 | 15 | 4 ms | 184 KB |
| 1 | sample 2 聚集型，均离岸远 | 答案正确 | 3 | 3 ms | 192 KB |
| 2 | 分散型，均跳不到，有在角上 | 答案正确 | 2 | 10 ms | 188 KB |
| 3 | 有一只在岸上，有一只在岛上，不能算在内 | 答案正确 | 3 | 4 ms | 172 KB |
| 4 | 最大N，sample1的复杂版，可选路径8条，后面要更新前面的最短路 | 答案正确 | 6 | 6 ms | 192 KB |
| 5 | 最小N，一步跳到岸 | 答案正确 | 1 | 4 ms | 184 KB |
3.旅游规划
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:
输入说明：输入数据的第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思路
Dijkstra算法变形，简单修改即可。这里图省事，就不套模板建图了（doge）。
AC code
#include <stdio.h>
#define MAXSIZE 505
const int inf = 0x7FFFFFF;
int N, M, S, D;
int dist[MAXSIZE], Cost[MAXSIZE], length[MAXSIZE][MAXSIZE],
money[MAXSIZE][MAXSIZE], visited[MAXSIZE];
void dijkstra() {
visited[S] = 1;
for (int i = 0; i < N - 1; ++i) {
int Min = inf, k;
for (int i = 0; i < N; ++i)
if (!visited[i] && dist[i] < Min) Min = dist[i], k = i;
if (Min == inf) break;
visited[k] = 1;
for (int i = 0; i < N; ++i)
if (!visited[i] && dist[i] > dist[k] + length[k][i]) {
dist[i] = dist[k] + length[k][i];
Cost[i] = Cost[k] + money[k][i];
} else if (!visited[i] && dist[i] == dist[k] + length[k][i] &&
Cost[i] > Cost[k] + money[k][i])
Cost[i] = Cost[k] + money[k][i];
}
}
int main() {
scanf("%d %d %d %d", &N, &M, &S, &D);
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) length[i][j] = money[i][j] = inf;
int city1, city2, len, cost;
while (M--) {
scanf("%d %d %d %d", &city1, &city2, &len, &cost);
length[city1][city2] = length[city2][city1] = len;
money[city1][city2] = money[city2][city1] = cost;
}
for (int i = 0; i < N; ++i) dist[i] = length[S][i], Cost[i] = money[S][i];
dist[S] = Cost[S] = 0;
dijkstra();
printf("%d %d\n", dist[D], Cost[D]);
return 0;
}| 测试点 | 提示 | 结果 | 分数 | 耗时 | 内存 |
|---|---|---|---|---|---|
| 0 | sample 最便宜的路不是最短路；输出2条最短路中最便宜的 | 答案正确 | 12 | 5 ms | 184 KB |
| 1 | 最小N和M | 答案正确 | 5 | 4 ms | 348 KB |
| 2 | 最大N，有多条等长等价的道路 | 答案正确 | 4 | 6 ms | 2236 KB |
| 3 | 最大N和M, 随机完全图 | 答案正确 | 4 | 46 ms | 2240 KB |
