PTA 最短路径（Dijkstra）2-1旅游规划 2-2直捣黄龙（最详细注释！）

目录

• • 2-1 旅游规划 (25 分)
  • 2-2 直捣黄龙 (30 分)

2-1 旅游规划 (25 分)

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:
输入说明：输入数据的第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 
#include 
using namespace std;
#define INF 0x3f3f3f3f
const int N = 501;
const int M = 25001;
int n, m, src, des;//n:点的个数，m:边数
int g[N][N]; //邻接矩阵：存放图中边的权重
int fee[N][N];//路费
int dis[N], vis[N];//dis[i]：src到i点的最短路径，vis[i]:标记最短路径已经确定的点void dijkstra(int s)
{memset(dis, 0x3f, sizeof(dis));//到每个点的距离初始化为无穷大memset(vis, 0, sizeof(vis));//0:未确定最短路径的点，1：已确定最短路径的点dis[s] = 0;for (int i = 0;i < n;i++)  //最多确定n个点的最短路径，中途找到des的最短路径就退出{int min = 0, mindis = INF;for (int j = 0;j < n;j++)  //从未确定最短路径的点中找出dis最小的点{if (vis[j] == 0 && dis[j] < mindis){min = j;mindis = dis[j];}}if (min == des)break;//说明到des的最短路径已确定，中止循环vis[min] = 1;for (int i = 0;i < n;i++)//更新点min的邻近点的最短路径{if (vis[i] == 0 && dis[min] + g[min][i] < dis[i]){dis[i] = dis[min] + g[min][i];   //若从s经过点min到i点比原先短，则更新fee[s][i] = fee[s][min] + fee[min][i];//顺带更新路费}else if (vis[i] == 0 && dis[min] + g[min][i] == dis[i] && fee[s][min] + fee[min][i] < fee[s][i]){fee[s][i] = fee[s][min] + fee[min][i];//若距离相同，但路费更低，则要更新路费}}}
}int main()
{memset(g, INF, sizeof(g));cin >> n >> m >> src >> des;for (int i = 0;i < m;i++){int s, d;cin >> s >> d;cin >> g[s][d] >> fee[s][d];g[d][s] = g[s][d]; //fee[d][s] = fee[s][d]; //这两句一开始没写，后面几个测试点都过不了！}dijkstra(src);cout << dis[des] << ' ' << fee[src][des];return 0;
}

2-2 直捣黄龙 (30 分)

本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。

输入格式：
输入第一行给出2个正整数N（2 ≤ N ≤ 200，城镇总数）和K（城镇间道路条数），以及己方大本营和敌方大本营的代号。随后N-1行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有K行，每行按格式城镇1 城镇2 距离给出两个城镇之间道路的长度。这里设每个城镇（包括双方大本营）的代号是由3个大写英文字母组成的字符串。

输出格式：
按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式己方大本营->城镇1->…->敌方大本营输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数，其间以1个空格分隔，行首尾不得有多余空格。

输入样例：
10 12 PAT DBY
DBY 100
PTA 20
PDS 90
PMS 40
TAP 50
ATP 200
LNN 80
LAO 30
LON 70
PAT PTA 10
PAT PMS 10
PAT ATP 20
PAT LNN 10
LNN LAO 10
LAO LON 10
LON DBY 10
PMS TAP 10
TAP DBY 10
DBY PDS 10
PDS PTA 10
DBY ATP 10
输出样例：
PAT->PTA->PDS->DBY
3 30 210

tips:
1.用map映射代号和数组下标
2.用栈和pre数组输出路径
3.最短路径条数求法见注释

呜呜呜花了一个下午，终于比较顺利地AC了这道题，内心开心极了呜呜！

我的答案

//长度最短 长度相同就经过点最多，点数相同就敌人数目最多
/*
最头疼的：求最短路径条数
开个数组short_cnt[N]，把起点的初始化为1
然后，更新dis[]时，short_cnt[i] = short_cnt[min];dis[min] + g[min][i] == dis[i]时，short_cnt[i] = short_cnt[i] + short_cnt[min];用一个例子执行一遍更好理解。
*/
#include 
#include 
#include 
#include
using namespace std;
#define INF 0x3f3f3f3f
const int N = 501;map<string, int> mp1;  //代号到数组下标的映射
map<int, string> mp2;  //数组下标映射到代号，便于后面输出路径int n, m;//n:点的个数，m:边数
string src, des;
int g[N][N]; //邻接矩阵：存放路径长度
int ene[N];//ene[i]:i对应城镇的敌人数
int dis_ene[N];//dis_ene[i]:从src到i路径杀敌总数
int dis[N], vis[N], pre[N], cnt[N];
//dis[i]：src到i点的最短路长，vis[i]:标记最短路径已经确定的点，pre[i]：路径的前一个点,cnt[i]:src到i经过的点数
int short_cnt[N];//相同长度路径条数void dijkstra(int s)
{memset(dis, 0x3f, sizeof(dis));//到每个点的距离初始化为无穷大memset(vis, 0, sizeof(vis));//0:未确定最短路径的点，1：已确定最短路径的点dis[s] = 0; dis_ene[s] = ene[s] = 0; cnt[s] = 0;short_cnt[0] = 1;for (int i = 0;i < n;i++)  //最多确定n个点的最短路径，中途找到des的最短路径就退出{int min = 0, mindis = INF;for (int j = 0;j < n;j++)  //从未确定最短路径的点中找出dis最小的点{if (vis[j] == 0 && dis[j] < mindis){min = j;mindis = dis[j];}}if (min == mp1[des])break;//说明到des的最短路径已确定，中止循环vis[min] = 1; for (int i = 0;i < n;i++)//更新点min的邻近点的最短路径{if (vis[i] == 0){if (dis[min] + g[min][i] < dis[i]){dis[i] = dis[min] + g[min][i];   //若从s经过点min到i点比原先短，则更新dis_ene[i] = dis_ene[min]+ene[i];//顺带更新杀敌数pre[i] = min;                //更新前一个点cnt[i] = cnt[min] + 1;       //更新点数short_cnt[i] = short_cnt[min];//更新最短路径条数}else if (dis[min] + g[min][i] == dis[i]) {short_cnt[i] = short_cnt[i] + short_cnt[min];if (cnt[i] < cnt[min] + 1)    //若长度相同，但经过点数更多，也更新{dis_ene[i] = dis_ene[min] + ene[i];pre[i] = min;cnt[i] = cnt[min] + 1;}else if (cnt[i] == cnt[min] + 1 && dis_ene[i] < dis_ene[min] + ene[i])  //若点数也相同，杀敌数更多，也更新{dis_ene[i] = dis_ene[min] + ene[i];pre[i] = min;}}}}}
}int main()
{memset(g, INF, sizeof(g));cin >> n >> m >> src >> des;mp1[src] = 0;//起始点代号映射到下标0string name;for (int i = 1;i < n;i++){cin >> name;mp1[name] = i;//代号映射到数组下标mp2[i] = name;//数组下标映射到代号，便于后面输出路径cin >> ene[i];}for (int i = 0;i < m;i++){string s, d;int len;cin >> s >> d >> len;g[mp1[d]][mp1[s]] = g[mp1[s]][mp1[d]] = len;}dijkstra(0);stack<int> path_s;   //存放路径上点对应下标int current = mp1[des];do{path_s.push(current); //入栈current = pre[current];} while (current != 0);string path = src;string next;while (!path_s.empty()){next = mp2[path_s.top()];  //注意，top()只是返回引用，不是出栈path_s.pop();    //出栈path = path + "->" + next;}cout << path << endl;cout << short_cnt[mp1[des]] << ' ' << dis[mp1[des]] << ' ' <<dis_ene[mp1[des]];return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！