PAT-最短路径题目汇总(Dijkstra+DFS)
2019-07-29 本文已影响0人
木易yr
A1003、A1030、A1018，A1072、A1087、A1111
A1003
题意：给出N个城市(编号0～n-1)，M条无向边，每个城市中都有一定数目的救援小组，所有的边权已知。现在给出起点和终点，求从起点到终点的最短路径条数以及最短路径上的救援小组数目之和，如果有多条最短路径，则输出数目之和最大的。
样列解释
输入：5个城市,点权分别为1、2、1、5、3
0 1 1即v0-v1，边权为1，以此类推，列出所有边以及边权
输出：从0到2最短路径的长度为2，共有两条0->2 和0->1->2，两条路径上的点权之和分别为2和4，所以输出路径数为2(注意输出的是路径条数)，点权之和最大4
Sample Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output:
2 4
最短路径问题：Dijkstra
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXV=510;
const int INF=1000000000;
//n为顶点数，m为边数，st和ed分别为起点和终点
//G为邻接矩阵，weight为点权
//d[]记录最短距离，w[]，记录最大点权之和，num[]记录最短路径条数
int n,m,st,ed,G[MAXV][MAXV],weight[MAXV];
int d[MAXV],w[MAXV],num[MAXV];
bool vis[MAXV]={false};//访问
void Dijkstra(int s) {//s为起点
fill(d, d + MAXV, INF);
memset(num, 0, sizeof(num));
memset(w, 0, sizeof(w));
d[s] = 0;
w[s] = weight[s];
num[s] = 1;
for (int i = 0; i < n; i++) { //循环n次
int u = -1, MIN = INF; //u 使d[u]最小，MIN中存放该最小的d[u]
for (int j = 0; j < n; j++) {
if (vis[j] == false && d[j] < MIN) {
u = j;
MIN = d[j];
}
}
// 找不到小于inf的d[u]说明剩下的顶点和起点s不连通
if (u == -1) return;
vis[u] = true; // 标记u为已访问
for (int v = 0; v < n; v++) {
//如果v未访问&&以u为中介点可以使d[v]更优
if (vis[v] == false && G[u][v] != INF) {
if (d[u] + G[u][v] < d[v]) { //以u为中介点时能令d[u]变小
d[v] = d[u] + G[u][v]; //覆盖d[v]
w[v] = w[u] + weight[v]; //覆盖w[v]
num[v] = num[u]; //覆盖num[v]
} else if (d[u] + G[u][v] == d[v]) { //找到一条相同长度的路径
if (w[u] + weight[v] > w[v]) { //以u为中介点时点权之和更大
w[v] = w[u] + weight[v]; //w[v]继承自w[u]
}
//注意最短路径与点权无关，必须写在外面
num[v] += num[u];
}
}
}
}
}
int main() {
//#ifndef ONLONE_JUDGE
// freopen("data.txt","r",stdin);//输出调试
//#endif
scanf("%d%d%d%d",&n,&m,&st,&ed);
for (int i = 0; i <n ; i++) {
scanf("%d",&weight[i]);//读入点权
}
int u,v;
fill(G[0],G[0]+MAXV*MAXV,INF); //初始化图G
for (int i = 0; i <m ; i++) {
scanf("%d%d",&u,&v);
scanf("%d",&G[u][v]);//读入边权
G[v][u]=G[u][v];
}
Dijkstra(st);//算法入口
printf("%d %d\n",num[ed],w[ed]);//最短路径条数，最短路径中的最大点权
return 0;
}
A1030
题意：给定N个城市编号(0~n-1)，M条道路(无向边)，并给出M条道路的距离属性与花费属性。现在给定起点S与终点D，从起点到终点的最短路径，最短距离以及花费。注：如果有多条最短路径，选择花费最小的那条
Sample Input:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
Sample Output:
0 2 3 3 40
样例解释
输入：4个城市，5条边，起点为0，终点为3,最短路径有两条，0->1->3，0->2->3，花费分别为50和40，因此选择花费较小的那一条0->2->3
输出为 0 2 3 40
最短路径：Dijkstra+DFS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3fffffff;
int G[510][510],cost[510][510];
//G是距离矩阵，cost为花费矩阵
//d为记录最短距离，minCost记录为最短路径上的最小花费
int n,m,st,ed,d[510],minCost=inf;
bool vis[510]={false};
vector<int>pre[510];//前驱
vector<int>tempPath,path;//临时路径及最有路径
void Dijkstra(int s){// s为起点
fill(d,d+510,inf);//fill函数将整个d数组赋值为INF
d[s]=0;//起点到达自身的距离,一开始设为0
for (int i = 0; i <n ; ++i) {
int u = -1, MIN = inf;//u使d[u]最小，MIN存放最小的d[]最小
for (int j = 0; j < n; ++j) {//找到未访问的顶点中d[]最小的
if (vis[j] == false && d[j] < MIN) {
u = j;
MIN = d[j];
}
}
// 找不到小于inf的d[u]说明剩下的顶点和起点s不连通
if(u==-1)
return;
vis[u]= true;
for (int v = 0; v <n; ++v) {
if(vis[v]==false&&G[u][v]!=inf){
if(d[u]+G[u][v]<d[v])//以u为中介点使d [v]最小
{
d[v]=d[u]+G[u][v];//优化dv
pre[v].clear();//清空pre
pre[v].push_back(u);//u为v的前驱
} else if(d[u]+G[u][v]==d[v])//找到相同长度的路径
pre[v].push_back(u);//u为v的前驱之一
}
}
}
}
void DFS(int v){//v为当前结点
if(v==st)//递归边界，到达叶子结点(路径起点)
{
tempPath.push_back(v);
int tempCost=0;
for (int i = tempPath.size()-1; i >0 ; i--) {//倒着访问
int id=tempPath[i],idNext=tempPath[i-1];//当前结点及下个结点
tempCost+=cost[id][idNext];增加边//id->index的边权
}
if(tempCost<minCost){//如果当前路径的边权之和更小
minCost=tempCost;//更新minCost
path=tempPath;//更新path
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for (int i = 0; i <pre[v].size() ; ++i) {
DFS(pre[v][i]);
}
tempPath.pop_back();
}
int main() {
//#ifndef ONLINE_JUDGE
// freopen("data.txt","r",stdin);
//#endif
scanf("%d%d%d%d",&n,&m,&st,&ed);
int u,v;
fill (G[0],G[0]+510*510,inf);//初始化图
fill(cost[0],cost[0]+510*510,inf);
for (int i = 0; i <m; ++i) {
scanf("%d%d",&u,&v);
scanf("%d%d",&G[u][v],&cost[u][v]);
G[v][u]=G[u][v];
cost[v][u]=cost[u][v];
}
Dijkstra(st);//入口
DFS(ed);//get最优路径
for (int i = path.size()-1; i >=0 ; i--) {//倒着输出
printf("%d ",path[i]);//
}
printf("%d %d\n",d[ed],minCost);//最短距离，最短路径上的最小花费
return 0;
}
A1018
题意：有条件的最短路问题变形，给出每个城市最大的容量CMAX(偶数)，且如果一个车站中的自行车数量恰好为CMAX的一半，则该车站处于完美状态，如果一个车站是满的或者是空的，那么控制中心就会携带或从路上收集一定数量的自行车前往该车站，使该车站达到“完美状态”，现给出Cmax，车站数目，问题车站编号Sp，无向边数M以及权重，求一条从PBMC(记为0号)到达问题车站的最短路径，输出需要从PBMC携带的自行车数目最少的，最短路径，到达车站后需要带回的自行车数目。如果最短路径有多条，那么选择从PBMC携带自行车最少的，如果仍然有多条，那么选择最后从问题车站带回的自行车数目最少的。注意：所有车站的调整过程在前往问题车站的过程中就调整完毕，带回时不再调整
做法：Dijkstra求最短路径+DFS回溯
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXV=510;
const int INF=1000000000;
int n,m,Cmax,Sp,numPath=0,G[MAXV][MAXV],weight[MAXV];
//最短路径，记录最少携带的数目，记录最少带回数目
int d[MAXV],minNeed=INF,minRemain=INF;
bool vis[MAXV]={false};
vector<int>pre[MAXV];
vector<int>tempPath,path;//
void Dijkstra(int s)
{
fill(d,d+MAXV,INF);
d[s]=0;
for(int i=0;i<=n;i++ )
{
int u=-1,MIN=INF;
for(int j=0;j<=n;j++)
{
if(vis[j]==false&&d[j]<MIN){
u=j;
MIN=d[j];
}
}
if(u==-1)
return;
vis[u]=true;
for(int v=0;v<=n;v++)
{
if(vis[v]==false&&G[u][v]!=INF){
if(d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
pre[v].clear();
pre[v].push_back(u);
}else if(d[u]+G[u][v]==d[v]){
pre[v].push_back(u);
}
}
}
}
}
void DFS(int v){
if(v==0){
tempPath.push_back(v);//递归边界，叶子结点
int need=0,remain=0;
for(int i=tempPath.size()-1;i>=0;i--)//倒着访问
{
int id=tempPath[i];
if(weight[id]>0){
remain+=weight[id]; //如果多了，说明需要带走，在原有的remain上叠加
}else {
if(remain>abs(weight[id])){//如果补给量足够，则从原有的剩余量中补给即可
remain-=abs(weight[id]);
}else{
need+=abs(weight[id])-remain;//不够的部分需要从PBCM携带
remain=0;//当前所有的自行车都用来补充了，所有剩余量为0
}
}
}
if(need<minNeed){
minNeed=need;
minRemain=remain;
path=tempPath;
}else if(need==minNeed&&remain<minRemain){
//如果携带的数目相同，但是带回的数量少
minRemain=remain;
path=tempPath;
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for(int i=0;i<pre[v].size();i++)
{
DFS(pre[v][i]);
}
tempPath.pop_back();
}
int main()
{
scanf("%d%d%d%d",&Cmax,&n,&Sp,&m);
int u,v;
fill(G[0],G[0]+MAXV*MAXV,INF);
for(int i=1;i<=n;i++){
scanf("%d",&weight[i]);
weight[i]-=Cmax/2;
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
scanf("%d",&G[u][v]);
G[v][u]=G[u][v];
}
Dijkstra(0);
DFS(Sp);
printf("%d ",minNeed);
for(int i=path.size()-1;i>=0;i--)
{
printf("%d",path[i]);
if(i>0)
printf("->");
}
printf(" %d",minRemain);
return 0;
}
