ls学习笔记note36:单源最短路径问题(SSSP问题)+最长路径问题
paperghost_ls · · 个人记录
观前提示:推荐洛谷日报学图论，你真的了解最短路吗？、浅谈Dijkstra、dijkstra 详解、SPFA算法的玄学方法和SPFA算法教学还有图论的小技巧以及扩展
很惊讶的发现，原来我之前都没写过单源最短路径的博客呢
所以，今天我们来讲一讲最短路的模板 有种不好的预感感觉这个专题又要我肝很久
废话不多说，先来看看题
单源最短路径模版
【题意】
给出一个图，起始点是1，结束点是N，边是双向的。求点1到点N的最短距离。哈哈，这就是标准的最短路径问题。 【输入格式】
第一行为两个整数N（1≤N≤10000）和M（0≤M≤200000）。N表示图中点的数目，M表示图中边的数目。
下来M行，每行三个整数x，y，c表示点x到点y之间存在一条边长度为c。（x≠y,1≤c≤10000）【输出格式】
输出一行，一个整数，即为点1到点N的最短距离。
如果点1和点N不联通则输出-1。【样例1输入】
2 1
1 2 3【样例1输出】
3【样例2输入】
3 3
1 2 5
2 3 5
3 1 2【样例2输出】
2【样例3输入】
6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 6 6
5 6 9【样例3输出】
20求单源最短路径有Dijkstra、Bellman-Ford、SPFA等算法。因为SPFA是用单调队列优化过的Bellman-Ford，所以这里对Bellman-Ford不再赘述，重点讲一下Dijkstra和SPFA两个算法
先来说一下这两个算法分别的优点吧：
Dijkstra:比较快，适合用于稠密图，但不能处理负权边
SPFA:适合用于稀疏图，可以处理负权边，还能判断负环，但是在各大竞赛中经常被卡
现在来讲讲题目
一、SPFA算法
我个人比较喜欢用SPFA，主要是用了将近一年了，所以对SPFA比较熟悉，先来讲讲SPFA
SPFA一般时间复杂度为O(kE)，k是一个小常数，看起来是一个很好的情况，但是他最坏情况下却是O(VE) (|V|=n,|E|=m)。据说2018年NOI出题人就卡了SPFA，导致100分的代码变成了60分。因此，OI界仍在流传下面这张当时出题人现场讲题时写下的东西:
雅蔑蝶！
先来看看SPFA是怎么样运行的
在运行之前，我得说明一下一些数组的意思:
list表示队列,head是队首，tail是队尾
d[i]表示起点到第i节点的最短距离
v[i]表示第i节点是否在队列里面
开始模拟算法:
首先自然是要建边的了，由于这是一个无向图——也就是说，这个图两点间虽然有边，但是既可以从节点A走到节点B，又可以从节点B走到节点A，而不是从节点A走到节点B，节点B却不能从这条边走到节点A，使得这条边没有明确的方向，即无向——所以，我们在建边的时候，要建双向边
一开始把所有点的d全部标记为无穷大(也就是图中的红色oo)，此时没有点入队，所以v都标记为false
起点到自身距离就是0，d[st]=0，第一个进队的也是起点
之后就是重复一些步骤了
1.如果队列空了，则不再循环
2.遍历所有以队首为起点的有向边(x,y)，如果d[y]>d[x]+该边的距离，更新d[y]
3.再接着询问，如果y不在队列里面就让y入队
4.队首退出队列最后判断终点是否可以到达。如果不可以到达的话d[ed]即为INF，输出-1，可以到达就输出d[ed]。结束
接下来，我们用一幅图，帮助我们更好地去理解这个算法
根据上面的步骤，节点1先进入队列。list={1}
访问以节点1(队首)为起点的边，先遍历到了节点5。因为d[5]=INF> d[1]+该边的距离=14,更新d[5]=14。因为节点5不在队列里面，所以节点5入队。list={1,5}
然后遍历到节点3，节点2。同理更新d[3]=9,d[2]=7。这两个节点也入队。list={1,5,3,2}
好了，节点1已经遍历完了它的所有"亲朋好友"，它已经完成了它的使命了，于是退队。list={5,3,2}
因为队列还没空，所以一切还得继续。新的队首节点5遍历以它为起点的边，分别遍历到节点6、节点3和节点1。因为d[6]=INF >d[5]+该边的距离=23，所以更新d[6]=23，节点6入队。但是d[3]=9 <d[5]+该边的距离=16，所以3不用更新。同样的，d[1]=0 <d[5]+该边的距离=28，所以1也不用更新。5完成使命以后退队 list={3,2,6}
同样，新的队首节点3开始遍历。它先遍历到节点5，发现d[5]=14 >d[3]+该边的距离=11，于是更新节点5，d[5]=11并重新入队 。它再遍历到节点4，因为d[4]=INF >d[3]+该边的距离=20，所以更新d[4]=20。它又遍历到节点2，可是d[2]=7 >d[3]+该边的距离=19，所以不变。最后遍历到节点1，那自然是不用改的了。3退队。list={2,6,5,4}
然后，节点2也开始了遍历。它遍历到节点4但是更新不了，遍历到节点3也更新不了，遍历到节点1更是更新不了，节点2也只好退队。list={6,5,4}
节点6开始了遍历。它遍历到节点5，d[5]=11 <d[6]+该边的距离=32，不更新。它又遍历到节点4，发现也更新不了，随即退出。list={5,4}
节点5故技重施，依次遍历6，3，1三个点，但是只有d[6]=23 >d[5]+该边的距离=20 ，也只能更新d[6]=20，节点6重新入队，然后就退队了。list={4,6}
节点4也更新不了节点6，3，2了，也退出了。list={6}
节点6没有其它边可以更新的了，只好退队。list={空}
队列空了，循环停止，遍历结束
最后输出要求的值即d[6]即可
回看一下这个过程，我来一一解释一下我觉得学最短路时有疑问的地方 可能是因为我太菜了
一、为什么队列空了就意味着所有点找到最短路径？
这个现在看来显而易懂。要先明确进入队列的条件。进入队列首先这个节点是要可以被更新，也就是有更短路径。既然队列空了，就说明所有点已经找到了最短路径，不能再找到更好的路径来更新了
二怎么建边？
咳，这个是一个大问题。不管是SPFA还是Dijkstra都是需要建边的。建边的方法有很多种，有邻接矩阵的建边、用vector建边等方法、邻接表的建边。但是我们用的可不是这几种方法，而是用一个叫做链式前向星的听起来就很高大上的东西。有人说链式前向星和邻接表思想差不多，只是邻接表更加灵活，链式前向星更加好写。在zsyz讲起来却没有那么有逼格了，在zsyz这玩意就是编目录
链式前向星，顾名思义，是一个链状的东西。链式前向星这个玩意呢还挺神奇，也很方便。它能在遍历所有以队首为起点的有向边时很容易地将这些边都调出来。具体怎么做呢，咱们先来看一段代码
struct node
{
int x,y,c,next;
}a[410000];int len,last[11000];
void ins(int x,int y,int c)
{
len++;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len;
}我先说明一下这些数值的表示的是什么。a数组就是用来存边的。x,y表示一条单向边的起点和终点，c表示距离，也就是权值，next就是下一条要遍历的是以这条边(a[i])的起点为起点的边。len就是存的边的个数，last[i]表示节点i最后存的是以节点i为起点的那一条单向边
好了，现在根据样例讲一讲这个具体是怎么操作的 这个样例真的是太合适了，赛高你high铁鸭子哒
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 6 6
5 6 9首先，第一条双向边过来存了。于是len++，len=1。然后1、2、7分别存入a[len=1]的x,y,c中。而这条边下一个要遍历的是last[1]记录的这一条边，于是a[1].next=last[1]=0。当前以节点1为起点的最后存的就是这一条边，所以记录下来last[1]=len=1。同时，因为是无向图双向边,所以要建立一条反过来的单向边。2、1、7分别存入，len=2。这条边下一个要遍历的是last[x]=last[2]=0也就是第0条边，存入a[2].next=last[2]=0。当前以节点2为起点的最后存的就是这一条边，所以记录下来last[2]=len=2
然后呢，第二条双向边过来存了。1、3、9同样存入a[len=3]的x,y,c中。这个时候，这条边下一个要遍历的是a[3].next=last[1]=1这一条边。而当前以节点1为起点的最后存的就是这一条边，所以记录下来last[1]=len=3。同时，要建立一条反过来的单向边。3、1、9分别存入，len=4。这条边下一个要遍历的是last[x]=last[3]=0也就是第0条边，存入a[4].next=last[3]=0。当前以节点3为起点的最后存的就是这一条边，所以记录下来last[3]=len=4
这个时候，又来了第三条双向边了。1、5、14存入,len=5。因为这条边下一个要遍历的是last[x]=last[1]=3也就是第3条边，所以存入a[5].next=last[1]=3。当前以节点1为起点的最后存的就是这一条边，所以记录下来last[1]=len=5。同时，建立一条反过来的边。5、1、14分别存入，len=6。这条边下一个要遍历的是last[x]=last[5]=0也就是第0条边，存入a[6].next=last[5]=0。当前以节点5为起点的最后存的就是这一条边，所以记录下来last[5]=len=6
突然，来了第四条双向边。2、3、10存入,len=7。这条边下一个要遍历的是last[x]=last[2]=2也就是第2条边，所以存入a[7].next=last[2]=2。当前以节点2为起点的最后存的就是这一条边，所以记录下来last[2]=len=7。同时，建立一条反过来的边。3、2、10分别存入，len=8。这条边下一个要遍历的是last[x]=last[3]=4也就是第4条边，存入a[8].next=last[3]=4。当前以节点3为起点的最后存的就是这一条边，所以记录下来last[5]=len=8
眨眼间，又来了第五条双向边。2、4、15存入,len=9。这条边下一个要遍历的是last[x]=last[2]=7也就是第7条边，存入a[9].next=last[2]=7。当前以节点2为起点的最后存的就是这一条边，所以记录下来last[2]=len=9。同时，建立一条反过来的边。4、2、15分别存入，len=10。这条边下一个要遍历的是last[x]=last[4]=0也就是第0条边，存入a[10].next=last[4]=0。当前以节点4为起点的最后存的就是这一条边，所以记录下来last[4]=len=10
弹指间，来了第六条双向边。同样的，3、4、11存入,len=11。这条边下一个要遍历的是last[x]=last[3]=8也就是第8条边，存入a[11].next=last[3]=8。当前以节点3为起点的最后存的就是这一条边，所以记录下来last[3]=len=11。同时，建立一条反过来的边。4、3、11分别存入，len=12。这条边下一个要遍历的是last[x]=last[4]=10也就是第10条边，存入a[12].next=last[4]=10。当前以节点4为起点的最后存的就是这一条边，所以记录下来last[4]=len=12
忽然，第七条双向边来了。同样，3、5、2存入,len=13。这条边下一个要遍历的是last[x]=last[3]=11也就是第11条边，存入a[13].next=last[3]=11。当前以节点3为起点的最后存的就是这一条边，所以记录下来last[3]=len=13。同时，建立一条反过来的边。5、3、2分别存入，len=14。这条边下一个要遍历的是last[x]=last[5]=6也就是第6条边，存入a[14].next=last[5]=6。当前以节点5为起点的最后存的就是这一条边，所以记录下来last[5]=len=14
过了一会，第八条双向边来了。同理，4、6、6存入,len=15。这条边下一个要遍历的是last[x]=last[4]=12也就是第12条边，存入a[15].next=last[4]=12。当前以节点4为起点的最后存的就是这一条边，所以记录下来last[4]=len=15。同时，建立一条反过来的边。6、4、4分别存入，len=16。这条边下一个要遍历的是last[x]=last[6]=0也就是第0条边，存入a[16].next=last[6]=0。当前以节点6为起点的最后存的就是这一条边，所以记录下来last[6]=len=16
最后，第九条双向边来了。5、6、9存入,len=17。这条边下一个要遍历的是last[x]=last[5]=14也就是第14条边，存入a[17].next=last[5]=14。当前以节点5为起点的最后存的就是这一条边，所以记录下来last[5]=len=17。同时，建立一条反过来的边。6、5、9分别存入，len=18。这条边下一个要遍历的是last[x]=last[6]=16也就是第16条边，存入a[18].next=last[6]=16。当前以节点6为起点的最后存的就是这一条边，所以记录下来last[6]=len=18
自此，存边就结束了，我们来看一看存边以后怎样
a[0].x=0 a[0].y=0 a[0].c=0 a[0].next=0
a[1].x=1 a[1].y=2 a[1].c=7 a[1].next=0
a[2].x=2 a[2].y=1 a[2].c=7 a[2].next=0
a[3].x=1 a[3].y=3 a[3].c=9 a[3].next=1
a[4].x=3 a[4].y=1 a[4].c=9 a[4].next=0
a[5].x=1 a[5].y=5 a[5].c=14 a[5].next=3
a[6].x=5 a[6].y=1 a[6].c=14 a[6].next=0
a[7].x=2 a[7].y=3 a[7].c=10 a[7].next=2
a[8].x=3 a[8].y=2 a[8].c=10 a[8].next=4
a[9].x=2 a[9].y=4 a[9].c=15 a[9].next=7
a[10].x=4 a[10].y=2 a[10].c=15 a[10].next=0
a[11].x=3 a[11].y=4 a[11].c=11 a[11].next=8
a[12].x=4 a[12].y=3 a[12].c=11 a[12].next=10
a[13].x=3 a[13].y=5 a[13].c=2 a[13].next=11
a[14].x=5 a[14].y=3 a[14].c=2 a[14].next=6
a[15].x=4 a[15].y=6 a[15].c=6 a[15].next=12
a[16].x=6 a[16].y=4 a[16].c=6 a[16].next=0
a[17].x=5 a[17].y=6 a[17].c=9 a[17].next=14
a[18].x=6 a[18].y=5 a[18].c=9 a[18].next=16
last[0]=0
last[1]=5
last[2]=10
last[3]=13
last[4]=15
last[5]=17
last[6]=18接下来我们来讲讲如何调用
给出一段代码
int x=list[head];
for(ri k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(d[y]>d[x]+a[k].c)
{
d[y]=d[x]+a[k].c;
if(!v[y])
{
v[y]=true;
list[tail++]=y;
if(tail==n+1)tail=1;
}
}
}当队首只有节点1的时候，list={1}时，代码中的x就是1了，节点1开始遍历。进入一个for循环，k=last[x]=last[1]=5。于是,代码中的y就是a[k].y=a[5].y=5了。对照上面列出的那一份表，可以看出，这个a[5]正是以节点1为起点存的最后一条边。因为d[5]=INF >d[1]+a[5].c=0+14=14 ，所以更新d[5]=14并入队
然后，k=a[k].next=a[5].next=3
发现了吗？这个next其实就是把上一条存的边作为下一次要遍历的边，因为我们是要从以节点i为起点的最后建的边开始，一直遍历到以节点i为起点的第一条边，所以这个next存的是上一次建的边，却是我们下一次要遍历的边。这也是为什么我上面的"上一个"要粗体
所以，链式前向星就像一个链条，把这一次遍历的和下一次遍历的边扣在了一起，而不是把这一次遍历的和下两次、下三次甚至更多次的边联系在一次。你只能根据下一次要遍历的边，一环一环地往前遍历，直到遍历到最先建的那一条边为止
下面给出代码，看注释理解:
#include<cstdio>
#include<cstring>
#define ri register int
using namespace std;
const int INF=0X3f3f3f3f;
struct node
{
int x,y,c,next;
}a[410000];int len,last[11000];//存边
void ins(int x,int y,int c)//链式前向星建边
{
len++;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len;
}
int list[11000],head,tail;
bool v[11000];//判断是否在队列里
int d[11000];//记录最小距离
int st,ed;
int main()
{
int n,m;scanf("%d%d",&n,&m);
memset(last,0,sizeof(last));
for(ri i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
st=1;ed=n;//最好这样写，虽然题目的st和ed固定为1,n，但大部分单源最短路径并不固定起点终点
memset(v,false,sizeof(v));v[st]=true;
memset(d,INF,sizeof(d));d[st]=0;
list[1]=st;
head=1;tail=2;
//初始化
while(head!=tail)//队列还没有空
{
int x=list[head];//取队首
for(ri k=last[x];k;k=a[k].next)//遍历所有以队首为起点的有向边
{
int y=a[k].y;
if(d[y]>d[x]+a[k].c)//更新
{
d[y]=d[x]+a[k].c;
if(!v[y])//不在队里
{
v[y]=true;
list[tail++]=y;
//入队
if(tail==n+1)tail=1;//这个用来节省空间
}
}
}
list[head++]=0;//出队
if(head==n+1)head=1;//用来节省空间
v[x]=false;//出队
}
if(d[ed]==INF)printf("-1\n");//没有更新就是不能到达
else printf("%d\n",d[ed]);
return 0;
}给一个用邻接矩阵建边的做法吧，不过很慢的:
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=0X3f3f3f3f;
int a[1100][1100];//保存a[x][y]的值表示点x到点y这条边的距离
int list[11000],head,tail;
bool v[11000];//判断是否在队列中
int d[11000];//记录最短距离
int st,ed;
int main()
{
int n,m;scanf("%d%d",&n,&m);
memset(a,INF,sizeof(a));
for(int i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
if(a[x][y]>c)//有更大的值就更新
{
a[x][y]=c;
a[y][x]=c;
}
}
st=1;ed=n;
memset(v,false,sizeof(v));v[st]=true;
memset(d,INF,sizeof(d));d[st]=0;
list[1]=st;
head=1;tail=2;
while(head!=tail)
{
x=list[head];//取队首
for(int y=1;y<=n;y++)//重点理解！k首相等于和x相连的最后一条边的编号。那么倒数第二条和x相连的边的编号是多少呢？在a[最后一条].next可以找到
{
if(d[y]>d[x]+a[x][y])//更新
{
d[y]=d[x]+a[x][y];
if(!v[y])
{
v[y]=true;
list[tail++]=y;
if(tail==n+1)tail=1;
}
}
}
list[head++]=0;//退队
if(head==n+1)head=1;
v[x]=false;
}
if(d[n]==INF)printf("-1\n");
else printf("%d\n",d[ed]);
return 0;
}二、Dijkstra算法
Dijkstra其实我也不是很熟悉，我也是昨天(2020/7/24)学会的，而且只打了一次，大概讲讲我对Dijkstra算法的理解吧
Dijkstra的时间复杂度在没有堆优化的情况下是O(N2),在堆优化时达到了O((m+n)logm)。我还发了一个贴炸出两个管理问过这个问题，所以Dijkstra还是要学的 特别是在SPFA已经死了的情况下
在运行之前，我还得说明一下一些数组的意思:
d[i]表示起点到第i节点的最短距离
v[i]表示第i节点是否被遍历过了
开始模拟算法:
首先自然是要建边的了
首先把所有点的d全部标记为无穷大(也就是图中的红色oo)，此时没有点入队，所以v都标记为false
起点到自身距离就是0，d[st]=0，第一个进队的也是起点
之后也是重复一些步骤了
1.循环n-1遍，因为每次都必定且只会遍历一个点，而且最后一个点不用遍历了，如果是最后一个点可以到达的话是可以更新到的，而且必定最小
2.寻找离起点最近且没有被遍历过的点
3.标记这个点已被遍历过
4.遍历所有以这个点为起点的有向边(x,y)，如果d[y]>d[x]+该边的距离，更新d[y]最后判断终点是否可以到达。如果不可以到达的话d[ed]即为INF，输出-1，可以到达就输出d[ed]。结束
我们根据换一张图来演算一下
在这里起点是A，终点是C吧
初始化以后，进入循环。第一个遍历到的自然是起点A了，标记v[A]。然后，更新以节点E为起点所能遍历到的节点B、E、G。d[B]=0+20=0,d[E]=0+10=10,d[G]=0+15=15
第二个遍历到的是节点E(d[E]=10<d[G]=15<d[B]=20<d[D]=d[F]=d[C]=INF)，同样标记v[E]。更新节点B、D、F，d[B]=10+9=19,d[D]=10+4=14,d[F]=10+10=20
第三个遍历到的是节点D(d[D]=14<d[G]=15<d[B]=19<d[F]=20<d[C]=INF),标记D。更新节点B,C,F。d[B]=14+3=17,d[C]=14+9=23,d[F]=14+4=18
第四个遍历到的是节点G(d[G]=15<d[B]=17<d[F]=18<d[C]=23)，同样标记G。更新节点C。d[C]=15+7=22
第五个遍历到的是节点B(d[B]=17<d[F]=18<d[C]=22),标记B，但是17+7=24>d[C]=22,而节点F又遍历不到，所以什么都不更新
最后第六个遍历的是节点F(d[F]=18<d[C]=22),标记。更新节点C。d[C]=18+3=21。
已经遍历了n-1=7-1=6次了，所以循环停止，遍历结束
不难看出,Dijkstra运用了贪心的思想，每一次都是寻找离起点最近且还没有遍历过的点，当所有边长都是非负数的时候,全局最小值不可能再被其他节点更新。所以在找出的点x必然满足:d[x]已经是起点到x的最短路径，我们不断选择全局最小值进行标记和拓展,最终可以得到起点到每个节点的最短路径的长度
其它地方大体上我都讲过了，和SPFA没什么区别，直接看看代码怎么实现的吧：
#include<cstdio>
#include<cstring>
#define ri register int
using namespace std;
const int INF=0X3f3f3f3f;
struct node
{
int x,y,c,next;
}a[410000];int len,last[11000];
void ins(int x,int y,int c)
{
len++;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len;
}
bool v[11000];
int d[11000];
int st,ed;
int main()
{
int n,m;scanf("%d%d",&n,&m);
memset(last,0,sizeof(last));
for(ri i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
st=1;ed=n;
memset(v,false,sizeof(v));
memset(d,INF,sizeof(d));d[st]=0;
for(ri i=1;i<=n-1;i++)//遍历n-1次
{
int x=0;
for(ri j=1;j<=n;j++) //寻找最小且还没有遍历的节点
if(!v[j]&&d[j]<d[x])x=j;
v[x]=true;//标记
for(ri k=last[x];k;k=a[k].next)//更新
{
int y=a[k].y;
if(d[y]>d[x]+a[k].c)d[y]=d[x]+a[k].c;
}
}
if(d[ed]==INF)printf("-1\n");
else printf("%d\n",d[ed]);
return 0;
}Dijkstra堆优化
Dijkstra算法可以用二叉堆来优化，具体说是可以用小根堆来优化
WHY？
因为朴素Dijkstra算法最大的缺点就是在寻找最小且还没有遍历过的节点中浪费了太多时间。而堆恰好可以解决这个问题。C++的STL里的堆可以直接就帮你排序。如果我们用小根堆的话，就可以很方便的找最小且还没有遍历过的节点
所以，我们采用小根堆来解决
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define ri register int
using namespace std;
const int INF=0X3f3f3f3f;
struct node
{
int x,y,c,next;
}a[410000];int len,last[11000];
void ins(int x,int y,int c)
{
len++;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len;
}
priority_queue< pair <int,int> >Q;//第一维是距离(通过相反数变成小根堆)，第二维是节点编号
bool v[11000];
int d[11000];
int st,ed;
int main()
{
int n,m;scanf("%d%d",&n,&m);
memset(last,0,sizeof(last));
for(ri i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
st=1;ed=n;
memset(v,false,sizeof(v));
memset(d,INF,sizeof(d));d[st]=0;
Q.push(make_pair(0,1));//插入堆
while(Q.size())//堆里还有
{
int x=Q.top().second;Q.pop();//取堆首(最小)
if(v[x])continue;//可能会出现已经遍历过的点，遍历过就算了
v[x]=true;//标记
for(ri k=last[x];k;k=a[k].next)//更新
{
int y=a[k].y;
if(d[y]>d[x]+a[k].c)
{
d[y]=d[x]+a[k].c;
Q.push(make_pair(-d[y],y));//插入
}
}
}
if(d[ed]==INF)printf("-1\n");
else printf("%d\n",d[ed]);
return 0;
}补充
一、无具体源点问题
P2648 赚钱
题目描述
zzy现在决定环游中国，顺便赚点钱。zzy在一个城市最多只能赚D元，然后他可以选择退休也就是停止赚钱，或者去其它城市工作。当然，他可以在别处工作一阵子后又回到原来的城市再赚D元。这样的往返次数是没有任何限制的。
城市间有P条单向路径连接，共有C座城市，编号从1到C。路径i从城市Ai到城市Bi，在路径行走上不用任何花费。
zzy还可以乘飞机从某个城市飞到另一个城市。共有F条单向的航线，第i条航线是从城市Ji飞到另一座城市Ki，费用是Ti元。假如zzy身上没有现钱，他可以用以后赚的钱来付机票钱。
zzy可以从任何一个城市出发开始赚钱，并且选择在任何时候、任何城市退休。现在zzy想要知道，如果在工作时间上不做限制，那么zzy共可以赚多少钱呢？如果赚的钱也不会出现限制，那么就输出orz
输入格式
第一行，4个用空格分开的正整数，D，P，C，F。
第二行到P+1行，第i+1行包含2个用空格分开的整数，表示一条从城市Ai到城市Bi的单向路径。
接下来的F行，每行3个用空格分开的正整数，表示一条从城市Ji到城市Ki的单向航线，费用为Ti。
输出格式
如果zzy赚的钱没有限制，输出orz。如果有限制，那么就输出在给定的规则下zzy最多可以赚到的钱数。
输入输出样例
输入
100 3 5 2
1 5
2 3
1 4
5 2 150
2 5 120输出
250这种没有具体源点(如题中的“zzy可以从任何一个城市出发开始赚钱”)的问题其实还蛮常见的，记一记吧
首先，最暴力的方法自然就是枚举每一个点为源点，然后都跑一遍最短路，但这样是肯定不行的除非数据水。跑一遍最短路已经要用掉不少的时间了，再来多几次肯定超时，所以我们要用另一种方法:引进超级源点
这个超级源点具体说来，就是在原图之外再设一个点，并将这个点连向原图中所有的节点，每条边的边权为0。再以这个点为源点只跑一遍最短路就可以了
但是，要是在最短路中，这个方法还是不怎么可行，它会把所有点都改成0。这个方法在最长路应该有用(例如本题)。实在不行还是得一个个枚举
可以参考下面两幅图理解一下为什么可以这样做
这题主要的难点就是建立超级源点，想通这个就可以了
参考代码:
#include<cstdio>
#include<cstring>
#define ri register int
using namespace std;
const int INF=0X3f3f3f3f;
int max(int x,int y){return x > y ? x : y;}
int ans=-INF;
struct node
{
int x,y,c,next;
}a[1100];int len,last[510];
void ins(int x,int y,int c)
{
len++;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len;
}
int list[510],head,tail;
bool v[510];
int d[510];
int st;
int cnt[510];
int main()
{
int q,m,n,k;scanf("%d%d%d%d",&q,&m,&n,&k);
memset(last,0,sizeof(last));
for(ri i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y,q);
}
for(ri i=1;i<=k;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,q-c);
}
st=n+1;
for(ri i=1;i<=n;i++)ins(st,i,0);//建超级源点
memset(v,false,sizeof(v));v[st]=true;
for(ri i=1;i<=n;i++)d[i]=-INF;d[st]=q;
list[1]=st;
head=1;tail=2;
while(head!=tail)
{
int x=list[head];
cnt[x]++;
if(cnt[x]==n+1)//判断是否成环
{
printf("orz\n");
return 0;
}
for(ri k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(d[y]<d[x]+a[k].c)
{
d[y]=d[x]+a[k].c;
if(!v[y])
{
v[y]=true;
list[tail++]=y;
if(tail==n+2)tail=1;
}
}
}
list[head++]=0;
if(head==n+2)head=1;
v[x]=false;
}
for(ri i=1;i<=n;i++)ans=max(ans,d[i]);
printf("%d\n",ans);
return 0;
}二、最长路径问题
P1807 最长路
题目描述
设 G 为有 n 个顶点的带权有向无环图，G 中各顶点的编号为 1 到 n，请设计算法，计算图 G 中 <1,n> 间的最长路径。
输入格式
输入的第一行有两个整数，分别代表图的点数 n 和边数 m。
第 2 到第 (m+1) 行，每行 3 个整数 u, v, w，代表存在一条从 u 到 v 边权为 w 的边。
输出格式
输出一行一个整数，代表 1 到 n 的最长路。
若 1 与 n 不联通，请输出 −1。
输入输出样例
输入
2 1
1 2 1输出
1这道题和最短路的思想几乎一模一样，但是貌似也会用到最长路，特此记录，但不赘述
有直接硬算的最长路:
#include<cstdio>//这道模板题可能有负边，我就用SPFA来做
#include<cstring>
#include<vector>
#include<queue>
#define ri register int
using namespace std;
const int INF=0X3f3f3f3f;
struct node
{
int x,y,c,next;
}a[410000];int len,last[11000];
void ins(int x,int y,int c)
{
len++;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len;
}
int list[11000],head,tail;
bool v[11000];
int d[11000];
int st,ed;
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);//这题是有向边
}
st=1;ed=n;
memset(v,false,sizeof(v));v[st]=true;
for(ri i=1;i<=n;i++)d[i]=-INF;d[st]=0;
list[1]=st;
head=1;tail=2;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(d[y]<d[x]+a[k].c)//最短直接改成最长
{
d[y]=d[x]+a[k].c;
if(!v[y])
{
v[y]=true;
list[tail++]=y;
if(tail==n+1)tail=1;
}
}
}
list[head++]=0;
if(head==n+1)head=1;
v[x]=false;
}
if(d[ed]==-INF)printf("-1\n");
else printf("%d\n",d[ed]);
return 0;
}也有把边变成负数，求一遍最短路，然后再转回成正数的:
#include<cstdio>//这道模板题可能有负边，我就用SPFA来做
#include<cstring>
#include<vector>
#include<queue>
#define ri register int
using namespace std;
const int INF=0X3f3f3f3f;
struct node
{
int x,y,c,next;
}a[410000];int len,last[11000];
void ins(int x,int y,int c)
{
len++;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len;
}
int list[11000],head,tail;
bool v[11000];
int d[11000];
int st,ed;
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,-c);//转成负权边
}
st=1;ed=n;
memset(v,false,sizeof(v));v[st]=true;
memset(d,INF,sizeof(d));d[st]=0;
list[1]=st;
head=1;tail=2;
while(head!=tail)//求最短路
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(d[y]>d[x]+a[k].c)
{
d[y]=d[x]+a[k].c;
if(!v[y])
{
v[y]=true;
list[tail++]=y;
if(tail==n+1)tail=1;
}
}
}
list[head++]=0;
if(head==n+1)head=1;
v[x]=false;
}
if(d[ed]==INF)printf("-1\n");
else printf("%d\n",-d[ed]);//再转回来
return 0;
}题外话:
最短路是我比较喜欢的一个专题，前前后后写了几个有关最短路的博客。今天花了一整天的时间写出来这篇博客，却感不到一丝疲倦，反而越写越兴奋
以后可能会再来加一些奇奇怪怪的东西，有缘再见！
2020/7/24 16:55 完成最短路径的撰写
2020/7/28 10:50 增加最长路
2020/7/29 09:45 增加无具体源点的问题