最短路径两道题

最短路径两道题"/>

最短路径两道题

1 旅游规划

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

输入格式:

输入说明：输入数据的第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算法:用一个dist数组来记录当前状态下,原点到某一点的最短距离,然后没一步都走最短的那一步,直到所有的点都加入了路程,则循环结束,最后得到的dist即是原点到所有点的最短路径.(缺点,如果路径权值有负值,则该方法失效,可以用bellman 利用n次松弛得到情况)

本题要求在最短路相同的时候,取花费最少的情况,所以在dist更新时,如果新的dist值跟老的dist值相同的话,那么就用一个cost记录当前dist的花费,再去跟新的dist所需花费的cost比较,进而选取最优的解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int graph[505][505];
int dist[505];
int vis[505];
int cost[505][505];
int spend[505];
int n,m,s,d;
int inf=1<<30;
int findmindist()
{	int min=inf;int pos=-1;int mincost=-1;for(int a=0;a<n;a++){if(!vis[a]&&dist[a]!=inf){if(dist[a]<min){pos=a;min=dist[a];mincost=spend[a];}else if(dist[a]==min){if(spend[a]<mincost){pos=a;mincost=spend[a];}}}}if(min==inf)return -1;else return pos;
}
int main()
{cin>>n>>m>>s>>d;for(int a=0;a<n;a++)//数据初始化,保证所有值都足够大{dist[a]=inf;}for(int a=0;a<m;a++){int x,y;cin>>x>>y;int wei,co;cin>>wei>>co;graph[x][y]=wei;graph[y][x]=wei;cost[x][y]=co;cost[y][x]=co;}dist[s]=0;spend[s]=0;//第一个点从s出发while(1)//循环开始{int pos=findmindist();if(pos==-1)break;vis[pos]=1;for(int a=0;a<n;a++){int i=graph[pos][a];if(i!=0&&vis[a]==0){if(dist[a]>dist[pos]+i){dist[a]=dist[pos]+i;spend[a]=spend[pos]+cost[pos][a];}else if(dist[a]==dist[pos]+i){if(spend[a]>spend[pos]+cost[pos][a]){spend[a]=spend[pos]+cost[pos][a];}}}}}cout<<dist[d]<<' '<<spend[d];
}

2,哈利波特的咒语 

哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是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算法:用来求任意两点的最短路径方法是dp,从0-n来规定两个点中间可以走的最小序数

思路:计算出每只动物所需的最长咒语,再从中找出最短的即可,如果在最后的循环中,发现一个值是inf则说明不能满足任何一个动物都可以变成其他动物,进而输出0

dp算式:

 注意!此题需要用加法,如果将两个1<<30加起来,会出现负号,进而导致整个题出错!

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int graph[105][105];
int n,m;
int inf=10000;
int main()
{cin>>n>>m;for(int a=1;a<=n;a++)for(int b=1;b<=n;b++){if(a==b)graph[a][b]=0;else graph[a][b]=inf;}for(int a=1;a<=m;a++){int x,y;cin>>x>>y;int weight;cin>>weight;graph[x][y]=graph[y][x]=weight;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);}int ce=0;int pos=-1,ans=inf;for(int a=1;a<=n;a++){int max=0;for(int b=1;b<=n;b++){if(graph[a][b]==inf){ce=1;break;}if(graph[a][b]>max)max=graph[a][b];}if(max<ans){pos=a;ans=max;}}if(ce==1)cout<<0;else cout<<pos<<" "<<ans;
}