【图论】【最短路】【SPFA】廉价最短路径

本文主要是介绍【图论】【最短路】【SPFA】廉价最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

图是由一组顶点和一组边组成的。一条边连接两个顶点。例如，图1表示了一个有4个顶点V、5条边的图。图中，每条边e是有方向的，方向从起点到终点，并且每条边都有价值。用整数0,1,…,m-1可以表示一个有m个顶点的图。

一条路径连接了一个点Vi和另一个点Vj，其方向与经过的一系列边的方向一致。路径的长度是途经边的条数，路径的费用是边价值的总和。对于一个给定的图，你的任务是在所有最短路径中，找出需要最少费用的连接V0和V1的路径。一个需要最少费用的最短路径称之为廉价最短路径。
让我们重新考虑图1，从0到1的最短路径是只含一条边的路径0→1，费用是10。当然，还有更便宜的路：0→2→1和 0→3→1，但是它们比第一条路径长(有2条边)。所以，0→1是廉价最短路径。
看一下另一个例子，图2，它有2条最短路径，其长度是2，路径0→3→1(费用=4)比路径0→2→1(费用=5)花费少。还用另一条路径0→2→3→1(费用=3)，虽然便宜但是很长。所以，廉价最短路径是0→3→1。

输入

输入文件第一行有两个整数m和n，用一个空格隔开，其中，m是顶点数，而n是边数。接下来的n行给出所有的边及其价值，每行有3个整数(相邻两个整数间有一个空格)，表示起点，终点和边的价值。顶点最多有100个，编号在0到99之间。边最多有1000条，其价值在0到2^15-1之间。

输出

输出文件仅有一行包含一个整数，即V0→V1的廉价最短路径的费用。当出现有多个廉价最短路径的情况时，它们的费用是一样的。

输入样例

输出样例

思路

直接用SPFA
然后改一下判断

#include<Algorithm>
#include<Iostream>
#include<Cstring>
#include<Cstdio>
#include<Cmath>
#include<Queue>
using namespace std;
struct whw
{int w,h,t;
}wh[200025];
int Ans[2][225],B[225],h[225];
int n,m,x,y,z,t;
void hw(int x,int y,int z)
{wh[++t]=(whw){y,h[x],z};h[x]=t;}
void SPFA()
{memset(Ans,0x3f,sizeof(Ans));queue<int>A;A.push(0);B[0]=0;Ans[0][0]=Ans[1][0]=0;while(A.size()){x=A.front(); A.pop();for(int i=h[x],y=wh[h[x]].w;i;i=wh[i].h,y=wh[i].w)if(Ans[0][x]+1<Ans[0][y]//如果走的步数更少|| Ans[0][y]==1061109567//如果没走过|| (Ans[0][x]+1==Ans[0][y]//如果相同步数&& Ans[1][x]+wh[i].t<Ans[1][y]))//且价值更小{Ans[1][y]=Ans[1][x]+wh[i].t;Ans[0][y]=Ans[0][x]+1;if(!B[y]){B[y]=1;A.push(y);}}B[x]=0;}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;++i){scanf("%d%d%d",&x,&y,&z);hw(x,y,z);}SPFA();printf("%d",Ans[1][1]);return 0;
}