首页 > 其他分享 >最短路

最短路

时间：2023-06-01 19:56:01浏览次数：34  
标签：idx int 短路 memset st sizeof include

新的相关知识

1.链式前向星，用于存图

链式前向星（加快图的搜索）_早睡身体好_的博客-CSDN博客


int e[N],ne[N],w[N],h[N],idx;

void add(int a,int b,int c){
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}

遍历
for(int i = h[t];i != -1;i = ne[i]){
	int j = e[i];
	
	}
}

2.优先队列，

优先队列，默认从大到小排序
加greater从小到大
q.push时，push一个负数，就可以省下写从小到大优先队列的功夫

3.cout的参数设置

1）fixed和setpricision()在iomanip 库中
2）c++98的sqrt参数必须是double类型。

4.负环

负环详解 - 子谦。 - 博客园 (cnblogs.com)
图上的最短路都是确定的。但是一旦图上有一个负环，s�到t�的最短路就会不远千里的去覆盖上这个环（只要能够到达），并且不厌其烦的走上一遍又一遍。由于负环的边权和是负的，并且它是一个环，也就是说走一遍和走无数遍都停留在进入的那个点。那么最短路每经过一次这个负环，这个费用都会缩小一点，如果经过了无数次，也就是无穷小，也就是不存在最短路。
//当然这里有一个限定，就是每个点经过的次数不能超过1次。

应该就是用st数组来实现这个点。

在SPFA中，每个点最多被其他n−1个点各收紧一次，如果被收紧了n次，显然是不合理的。那么我们就记录每个点被收紧的次数，有任何点超过n次，就可以判定存在负环了，如果SPFA成功运行完了，就证明不存在负环。

cnt[j] >=- n 时

5.邻接矩阵

以为是什么新东西，原来早就看过
邻接矩阵_diviner_s的博客-CSDN博客
用二维数组存图，

f[N][N]
f[i][j] =1 表示i到j有一条权值为1的边。
i维表示出度，以i为起点有出度为1的边
j维表示入度，以j为起点有入度为1的边。

dijkstra

与spfa区别

与spfa区别：
1）起点不用特别设置bool值，结果发现spfa的起点设置bool完全是多余的
结果发现我的理解有偏差·，求负环时可以去掉起点bool设置，但求最短路不行
2）要用优先队列，greater或less然后push负数
3）元素出队不需要改bool值
4）在遍历链式前向星前判元素bool
5）判队中元素为true直接continue；false则设为true

1.堆优化Dijkstra求最短路

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
int e[N],ne[N],w[N],h[N],idx;
int d[N],st[N];
void add(int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void dijkstra(){
    priority_queue<PII> q;
    q.push({0,1});
    d[1] = 0;
    while(q.size()){
        int t = q.top().second;
        q.pop();
        if(st[t] ) continue;
        st[t] = true;
        for(int i = h[t];i != -1;i = ne[i]){
            int j= e[i];
            if(d[j] > d[t] + w[i]){
                d[j] = d[t] + w[i];
                q.push({-d[j],j});
            }
        }
    }
}
void init(){
    idx = 0;
    memset(h,-1,sizeof h);
    memset(st,0,sizeof st);
    memset(d,0x3f,sizeof d);
}

void solve(){
    init();
    int n,m;
    cin >> n >> m;
    for(int i =1;i <= m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    dijkstra();
    if(d[n] != 0x3f3f3f3f)
    cout << d[n] << endl;
    else cout << -1 << endl;
}
int main(){
    solve();
    return 0;
}

套路 图上一个点到其他点的最短路

前提：

图上一个点到其他点的最短路

情景

输出一个整数，表示 1 号点到 n 号点的最短距离。

应对：

与spfa区别：
1）起点不用特别设置bool值，结果发现spfa的起点设置bool完全是多余的
结果发现我的理解有偏差·，求负环时可以去掉起点bool设置，但求最短路不行
2）要用优先队列，greater或less然后push负数
3）元素出队不需要改bool值
4）在遍历链式前向星前判元素bool
5）判队中元素为true直接continue；false则设为true

2.堆优化silver cow party(正反向同时建图)

链接

Silver Cow Party

代码

题解代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

#define MAXN 1010
#define MAXM 200010

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

const int inf=0x3f3f3f3f;

int n,m,x;

int head[2][MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
h，e，ne，w，id
int dist[2][MAXN];

int vis[MAXN];
写成二维，保存两种建图的数据
void add(int op,int a,int b,int c)
{
    ed[idx]=b;
    val[idx]=c;
    nex[idx]=head[op][a];
    head[op][a]=idx++;
    因为是用a来哈希访问到idx，所以idx值怎么样根本无所谓
}
void dijkstra(int start,int op)
{
	两种dijkstra的起点不同，通过传入参数来解决。
    memset(dist[op],0x3f,sizeof(dist[op]));二维数组只初始化一维。没必要，但没学过写来看看
    memset(vis,0,sizeof(vis));
    priority_queue<PII > q;
    q.push({0,start});
    dist[op][start]=0;
    while(q.size()>0)
    {
        PII temp=q.top();
        q.pop();
        int temp_dis=temp.first,temp_pos=temp.second;
        if(vis[temp_pos]==1)
            continue;
        vis[temp_pos]=1;

        for(int i=head[op][temp_pos];i!=-1;i=nex[i])
        {
            int j=ed[i];
            if(vis[j]==1)
                continue;
            if(dist[op][j]>dist[op][temp_pos]+val[i])
            {
                dist[op][j]=dist[op][temp_pos]+val[i];
                q.push({-dist[op][j],j});
            }
            谜之操作，直接让temp存q.top().second就好了。
        }        
    }
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    cin >> n >> m >> x;
    memset(head,-1,sizeof(head));

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(0,a,b,c);//正向建边(求终点到每个点的距离)——回家
        add(1,b,a,c);//反向建边(求每个点到终点的距离)——启程
    }

    dijkstra(x,0);
    dijkstra(x,1);
    谜之操作，一个把op写前面，一个把op写后面。

    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,dist[0][i]+dist[1][i]);
找最大
    cout << res << endl;



    return 0;
}

模仿

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N =1e6 + 10;
int h[2][N],e[N],ne[N],w[N],idx;
int d[2][N],st[N];
void add(int op,int a,int b,int c){
	e[idx] = b,w[idx] = c,ne[idx] = h[op][a] ,h[op][a] = idx++;
}
void dijkstra(int op,int s){
	memset(d[op],0x3f,sizeof d[op]);
	memset(st,0,sizeof st);
	priority_queue<PII> q;
	
	q.push(make_pair(0,s));
	未知起点变为s
	d[op][s] = 0;
	while(q.size()){
		int t = q.top().second;
		q.pop();
		if(st[t] ) continue;
		st[t] = true;
		for(int i = h[op][t];i != -1;i = ne[i]){
			int j = e[i];
			if(d[op][j] > d[op][t] + w[i]){
				d[op][j] = d[op][t] + w[i];
				q.push(make_pair(-d[op][j],j));
			}
		}
	}
}
int main(){
	 int n,m,ed;
	 memset(h,-1,sizeof h);
	 cin >> n >> m >> ed;
	 for(int i = 1;i <= m;i++){
	 	int a,b,c;
	 	cin >> a >> b >> c;
	 	add(0,a,b,c);
	 	add(1,b,a,c);
	 }
	 dijkstra(0,ed);
	 dijkstra(1,ed);
	 int res= 0;
	 for(int i = 1;i <= n;i++){
	 	res = max(res,d[0][i] + d[1][i]);
	 }
	 cout << res << endl;
	 return 0;
}

套路 求有向图上点到一个点的来回的最短路

如果是无向图就直接最短路 * 2
但是有向图，需要分开求来与回的两段最短路

前提：求有向图上点到一个点的来回的最短路。

应对

朴素做法，求出图上点到n的最短路，然后再求n到图上点的最短路，后一步需要n次dijkstra，复杂度很高。所以需要变化

实际做法正向建图之后再反向建图，用一个二维数组来保存两个图，通过一个op来区分两个图的add和dijkstra

具体点就是把h，d，add，dijkstra变成二维。

情景

N 头牛要去参加在某农场举行的一场编号为 X 的牛的派对。

有 M 条有向道路，每条路长 Ti；每头牛参加完派对后都必须回到家，每头牛都会选择最短路径。

求这 N 头牛的最短路径（一个来回）中最长的一条的长度。

习题1.堆优化Til the Cows Come Home（反向建图）

套路

前提：

图上其他点到一个点的最短距离

情景

Bessie从地标N到地标1所必须走的最小距离。
终点是地标1，N代表图上其他点。

所以dijkstra的初始点设为1.

代码

题解代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#define R register int
using namespace std;
const int manx=1e4+5;
int head[manx],d[manx];
bool vis[manx];
int n,m,k=0,s,e;
struct node{
    int v,next,w;
}a[manx];
void add(int u,int v,int w)
{
    a[++k].next=head[u];
    a[k].w=w;
    a[k].v=v;
    head[u]=k;
}
void dij()
{
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[s]=0;
    priority_queue<pair<int,int> >q;
    q.push(make_pair(0,s));
    while(q.size()){
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=a[i].next){
            int v=a[i].v,w=a[i].w;
            if(d[v]>d[u]+w) d[v]=d[u]+w,q.push(make_pair(-d[v],v));
        }
    }

}
int main()
{
    scanf("%d%d",&m,&n);
    e=1,s=n;
    反向建图，仍以1为流程起点
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
        无向边建图
    }
    dij();
    cout<<d[e];
    return 0;
}

模仿

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
int e[N],ne[N],w[N],h[N],idx;
int d[N],st[N];
void add(int a,int b,int c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void dijkstra(){
    priority_queue<PII> q;
    q.push({0,1});
    d[1] = 0;
    while(q.size()){
        int t = q.top().second;
        q.pop();
        if(st[t] ) continue;
        st[t] = true;
        for(int i = h[t];i != -1;i = ne[i]){
            int j= e[i];
            if(d[j] > d[t] + w[i]){
                d[j] = d[t] + w[i];
                q.push({-d[j],j});
                q里的d[j],只决定j在何时被读取到，只是决定了顺序，所以全员变成-数，然后再从小到大排序的效果等价于原来的从大到小排序
            }
        }
    }
}
void init(){
    idx = 0;
    memset(h,-1,sizeof h);
    memset(st,0,sizeof st);
    memset(d,0x3f,sizeof d);
}

void solve(){
    init();
    int n,m;
    cin >> n >> m;
    for(int i =1;i <= m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    dijkstra();
    if(d[n] != 0x3f3f3f3f)
    cout << d[n] << endl;
    else cout << -1 << endl;
}
int main(){
    solve();
    return 0;
}

spfa

前提条件

可能有负权边，判断负环

应对，与dijkstra区别

与堆优化dijkstra相像，
区别在于
1）元素出队时要判false，
2）st[j]要在dist[j] 需要更新时才判，如果false要true然后入队
3）起点要设为true ，多余。

1.spfa求最短路

AcWing 851. spfa求最短路 - AcWing

代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];点到起点距离
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    链式前向星
    idx边的数量
    e第idx条边的终点
	w第idx条边的权值
	ne第idx条边的h[a]
	与当前边起点相同的上一条边的编号
	h[a]起点为a的边的编号。
	
}
存一条起点a，终点b，边权c的边；
add1 2 1
add2 3 1
add3 1 1
e[] = {2,1,3,2,1,3};
w[] = {1,1,1,1,1,1};
ne[] = {h[1]=0,h[2]=0,h[2]=2,h[3]=0,h[3]=4,h[1]=1}
idx 2 ,h[1] = 1 
idx 3 ,h[2] = 2
idx 4 ,h[2] = 3;
idx 5 ,h[3] = 4;
idx 6 ,h[3] = 3;
idx 7 ,h[1] = 6;
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
	起点初始化为0，其余正无穷。
	
    queue<int> q;
    q.push(1);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i])
        {
        初始值是起点为t的边的编号
		i = ne[i],获得起点为t的边下一条边的编号。
            int j = e[i];
			j = e[i],起点为t的边对应的终点
            if (dist[j] > dist[t] + w[i])
            找到更小走法，更新
            {
                dist[j] = dist[t] + w[i];
                意义不明
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    int t = spfa();

    if (t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

例题2青蛙 给点建图，最大边的最小值

AcWing 4240. 青蛙 - AcWing

注意

fixed和setpricision()在iomanip 库中
c++98的sqrt参数必须是double类型。

代码

题解代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 4e4+10;
用点建无向图需要 n*n*2次，
PII p[N];
存点
因为题目只给了点，没有给边，要存点坐标
int e[N],ne[N],w[N],h[N],idx;
bool st[N];
int d[N];

int getlen(PII a,PII b)
{
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
    存的时候存平方式，输出时再开根。
}
void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    编号idx终点，编号idx边权，编号idx下一条边编号，哈希，起点a边编号
}

void spfa()
{
    memset(st, false, sizeof st);
    memset(d,0x3f,sizeof d);
    dist数组，点到起点距离
    queue<int> q;
    q.push(1);
    st[1] = true;
    d[1] = 0;

    while(q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for(int i = h[t];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(d[j] > max(d[t],w[i]))
            为什么取最大值未知
            {
                d[j] = max(d[t],w[i]);
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

int main()
{
    int n;
    int t = 1;
    while(true)
    {
        cin>>n;
        if(n == 0) break;
        多组输入
        idx = 0;
        初始化idx
        for(int i = 1;i<=n;i++)
        {
            int x,y;
            cin>>x>>y;
            p[i] = {x,y};
        }
        memset(h, -1, sizeof h);
        for(int i =1;i<n;i++)
            for(int j = i+1;j<=n;j++)
            {
                int w = getlen(p[i],p[j]);
                PII数组
                输入点得到权值拼平方
                add(i,j,w);
                add(j,i,w);
            }
            建图
        spfa();
        cout<<"Scenario #"<<t<<endl;
        cout<<"Frog Distance = "<<fixed<<setprecision(3) <<(double)sqrt((double)d[2])<<endl;
        取消cout的科学计数法，设置保留位数
        补充：cout会四舍五入。
        cout<<endl;
        t++;
    }
}

作者：sklit8
链接：https://www.acwing.com/solution/content/106663/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

模仿代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <cmath>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 4e4 + 10;
排列型枚举点，大约枚举n*n/2次，乘2就是n*n
PII p[N];
int e[N],ne[N],w[N],h[N],idx;
bool st[N];
int d[N];
int getlen(PII a,PII b){
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y ) * (a.y - b.y) ;
}
void add(int a,int b,int c){
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void spfa(){
	memset(st,false,sizeof st);
	memset(d,0x3f,sizeof d);
	queue<int> q;
	q.push(1);
	st[1] = true;
	d[1] = 0;
	while(q.size()){
		int t = q.front();
		q.pop();
		st[t] = false;
		for(int i = h[t];i != -1;i = ne[i]){
			int j = e[i];
			if(d[j] > max(d[t],w[i])){
				d[j] = max(d[t],w[i]);
				if(!st[j]){
					q.push(j);
					st[j] = true;
				}
			}
		}
	}
	
}
int main(){
	int n;
	int t = 1;
	while(cin >> n && n){
		idx = 0;
		数组开得够小，但sg f，这次是重复定义变量
		初始化边数
		for(int i = 1;i <= n;i++){
			int x,y;
			cin >> x >> y;
			p[i] = {x,y};
			
		}
		读入PII point数组
		memset(h,-1,sizeof h);
		
		初始化上一个起点为a的边对应的编号
		for(int i  = 1;i < n;i++){
			for(int j = i+1;j <= n;j++){
				int w = getlen(p[i],p[j]);
				add(i,j,w);
				add(j,i,w);
				用下标可以访问点，所以直接用下标建图
			}
		}
		组合型枚举建图
		spfa();
		cout << "Scenario #" << t++ << endl;
		cout << "Frog Distance = " << fixed << setprecision(3) <<sqrt(d[2]) << endl;
		cout << endl;

	}
}

卡壳点：

st[t]= false 写成了 t = false
结果一直输出 0 -》 忘记调用spfa
数组开得够小，但sg f，这次是重复定义用作下标的变量

套路

1）只给点建图

排列型枚举建图
自己计算边权。
可以保存长度平方，最后再sqrt然后输出

2）前提条件 a至b路径中最长边的最小值

情景

第一个石头上的青蛙要到第二个石头上找另一个青蛙玩耍。

给定a与b

这只青蛙希望，它的跳跃过程中，单次跳跃的最长距离尽可能短。
请你计算并输出这个最长距离的最小可能值

要找出最小可能值，首先要先把最长距离全部找出来。
所以题目的意思是找所有路径中最长边的最小值

应对

1.因为要取max，所以起点dist 设为 -0x3f3f3f3f，保证第一次的max(d[t],w[i]) 会得到w[i]的值
2.遍历链式前向星时,d[j] 取min(d[j],max(d[t],w[i]))

if(d[j] > max(d[t],w[i]))
	d[j] = max(d[t],w[i]);

3.dist数组值初始化为0x3f3f3f3f
为了保证d[j] 没更新过时，一定会被更新，所以要初始化为0x3f3f3f3f

memset(d,0x3f,sizeof d);

3）无向边建图：

得到一条无向边，要把起点终点add一次，调换后再add一次

例题3货物运输，最小边的最大值

AcWing 4241. 货物运输 - AcWing

代码

题解代码（解析）

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1010,M=N*N;
剩空间的开发，感觉没必要
int h[N],ne[M],e[M],w[M],idx;

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    链式前向星的加边操作
}

int dis[M],st[M],n,m;
dist与bool st，点与边数量
typedef pair<int,int> PII;

void spfa()
{
    queue<int> q;
    dis[1]=0x3f3f3f3f;
    
    q.push(1);
    st[1]=1;
    while(q.size())
    {
        auto t=q.front();
        谜之auto
        q.pop();
        st[t]=0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
        链式前向星的遍历
            int j=e[i];
            if(dis[j]<min(dis[t],w[i]))
            {
                dis[j]=min(dis[t],w[i]);
                if(!st[j])
                {
                st[j]=1;
                q.push(j);
                }
            }
        }
    }
}

void init()
{
    idx=0;
    memset(h,-1,sizeof h);
    memset(dis,-0x3f,sizeof dis); 
    memset(st,0,sizeof st);
    偏好此种写法，
    适合检查
    否则容易漏初始化
}

void solve()
{
    init();
    谜之ll
    scanf("%lld %lld",&n,&m);

    while(m--)
    {
        int a,b,c;
        scanf("%lld %lld %lld",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }

    spfa();
    printf("%lld\n\n",dis[n]);
}
signed main()
{
    int t;   
    scanf("%lld",&t);
    for(int i=1;i<=t;i++)
    {
        printf("Scenario #%d:\n",i);
        solve();
    }
    return 0;
}

//作者：天后
//链接：https://www.acwing.com/solution/content/129977/
//来源：AcWing
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

太多谜点，稍微修改下

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=N*N;
int h[N],ne[M],e[M],w[M],idx;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;   
}
int dis[M],st[M],n,m;
void spfa()
{
    queue<int> q;
    dis[1]=0x3f3f3f3f;
    
    q.push(1);
    st[1]=1;
    while(q.size())
    {
        int t=q.front();
    
        q.pop();
        st[t]=0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
        
            int j=e[i];
            if(dis[j]<min(dis[t],w[i]))
            {
                dis[j]=min(dis[t],w[i]);
                if(!st[j])
                {
                st[j]=1;
                q.push(j);
                }
            }
        }
    }
}

void init()
{
    idx=0;
    memset(h,-1,sizeof h);
    memset(dis,-0x3f,sizeof dis); 
    memset(st,0,sizeof st);

}

void solve()
{
    init();
    
    scanf("%d %d",&n,&m);

    while(m--)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }

    spfa();
    printf("%d\n\n",dis[n]);
}
int main()
{
    int t;   
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        printf("Scenario #%d:\n",i);
        solve();
    }
    return 0;
}

//作者：天后
//链接：https://www.acwing.com/solution/content/129977/
//来源：AcWing
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

模仿代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e6 + 10;
int ne[N],e[N],w[N],h[N],idx;
int st[N],d[N];
void add(int a,int b,int c){
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void spfa(){
	queue<int> q;
	q.push(1);
	st[1] = 1;
	d[1] = 0x3f3f3f3f;
	while(q.size()){
		int t = q.front();
		q.pop();
		st[t]= 0;
		for(int i = h[t];i != -1;i = ne[i]){
			int j = e[i];
			if(d[j] < min(d[t],w[i])){
				d[j] = min(d[t],w[i]);
				if(!st[j]){
					st[j] = true;
					q.push(j);
				}
			}
		}
	}
}
void init(){
	memset(h,-1,sizeof h);
	memset(st,0,sizeof st);
	memset(d,-0x3f,sizeof d);
	idx = 0;
}
void solve(){
    init();
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    spfa();
    cout << d[n] << endl << endl;
}

int main(){
	int t;
	cin >> t;
	
	for(int i = 1;i <= t;i++){
        printf("Scenario #%d:\n",i);
				solve();
	}
	return 0;
}
卡壳点

忘记调用init
d[j]写成st[j];
卡cin: 1e6的边，需要scanf

seg def读边时写成读点，nm弄混

套路

1）a至b路径中最小边的最大值

情景

现在，要从点 1 到点 n 运货。
已知每条边的最大承重，请你计算一次最多可以运多少货物。

每行三个整数 a,b,c，表示点 a 和点 b 之间有一条无向边，最大承重为 c。

应对：

1.因为要取min，所以起点dist 设为 正无穷0x3f3f3f3f，保证第一次的min(d[t],w[i]) 会得到w[i]的值
2.遍历链式前向星时，d[j] 取max(d[j],min(d[t],w[i]))，与上一道例题相反

if(d[j] < min(d[t],w[i]))
	d[j] = min(d[t],w[i]);

3.dist数组值初始化为-0x3f3f3f3f
为了保证d[j] 没更新过时，一定会被更新，所以要初始化为-0x3f3f3f3f,与上一题相反。

memset(d,-0x3f,sizeof d);

例题4 货币交换，spfa判负环

AcWing 4242. 货币兑换 - AcWing

代码

题解代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

#define MAXN 110

using namespace std;

typedef long long ll;
typedef pair<double,double> PDD;
题目给的浮点数据，用double存
//const double eps=1e-8;
莫名奇妙的东西

int n,m,start;

double money;
int head[MAXN],ed[2*MAXN],nex[2*MAXN],idx;
PDD val[2*MAXN];

double dist[MAXN];
int vis[MAXN],cnt[MAXN];

void add(int a,int b,PDD c)
{
    ed[idx]=b;
    val[idx]=c;
    nex[idx]=head[a];
    head[a]=idx++;
}

int spfa()
{
    queue<int> q;
    q.push(start);

    vis[start]=1;

    while(q.size())
    {
        int temp=q.front();
        q.pop();

        vis[temp]=0;

        for(int i=head[temp];i!=-1;i=nex[i])
        {
            double rate=val[i].first,cost=val[i].second;
            int j=ed[i];
            //if(dist[j]+eps<(dist[temp]-cost)*rate)
            if(dist[j]<(dist[temp]-cost)*rate)
            {
            存价钱。如果有负环·就等于有正环
                dist[j]=(dist[temp]-cost)*rate;
                cnt[j]=cnt[temp]+1;
                存j的最短路经过了几条边。
                if(cnt[j]>=n)
                    return 1;
                    
                    spfa判负环
                    这里的语句看着是判持续增长的环
                if(vis[j]==0)
                {
                    vis[j]=1;
                    q.push(j);
                }
            }   
        }
    }
    return 0;
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    cin >> n >> m >> start >> money;
    货币种类，兑换点数量，初始种类，初始数量。
    memset(head,-1,sizeof(head));
    memset(dist,-0x3f,sizeof(dist));
	double的初始化也用0x3f
    for(int i=1;i<=m;i++)
    {
        int a,b;
        double rate1,rate2,cost1,cost2;
        兑换率，服务费
        cin >> a >> b >> rate1 >> cost1 >> rate2 >> cost2;
        add(a,b,make_pair(rate1,cost1));
        add(b,a,make_pair(rate2,cost2));
    }

    dist[start]=money;

    if(spfa()==1)
        cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

卡壳点，

没注意链式前向星数组要开二倍N

模仿代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2e2 + 10;
typedef pair<double,double> PDD;
int n,m,stat;
PDD w[N];
bool st[N];
int cnt[N];
double d[N];
	

double num;
int h[N],ne[N],e[N],idx;
void add(int a,int b,PDD c){
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int spfa(){
	queue<int> q;
	q.push(stat);
	st[stat] = 1;
	d[stat] = num;
	while(q.size()){
		int t = q.front();
		q.pop();
		st[t] = false;
		for(int i = h[t];i != -1;i = ne[i]){
			int j = e[i];
			double rate = w[i].first,cost = w[i].second;
			if(d[j] < (d[t] - cost) * rate){
			负环，小于时更新。
				d[j] = (d[t] - cost) * rate;
				cnt[j] = cnt[t] + 1;
				if(cnt[j] >= n){
					return 1;
				}
				if(!st[j]){
					st[j] = true;
					q.push(j);
				}
			}
		}
	}
	return 0;
}
int main(){
	cin >> n >> m >> stat >> num;
	memset(h,-1,sizeof h);
	//memset(d,-0x3f,sizeof d);
	判负环不需要初始化dist
	for(int i= 1;i <= m;i++){
		int a,b;
		double r1,r2,c1,c2;
		cin >> a >> b >> r1 >> c1 >> r2 >> c2 ;
		add(a,b,make_pair(r1,c1));
		add(b,a,make_pair(r2,c2));
	}

	if(spfa() == 1){
		cout << "YES" << endl;
		
	}
	else cout << "NO" << endl;
	return 0;
}

卡壳点

add时b写成a
变量重复定义
忘记初始化h

套路

情景

他想要通过先将自己手中的钱进行辗转兑换，最终再次换回 S� 货币的方式，让自己手中的钱变得更多。

与spfa联系

cnt d[j],dist,bool spfa
在spfa基础上，是用cnt数组来维护当前点最短路经过的边数量，与点数比较判断是否成环。
dist初始值无要求，可以不用初始化
d[j]更新变为取max
cnt
spfa作为bool函数返回1或0；

例题5 虫洞 spfa 判负环

AcWing 904. \(\color{Blue}{kuangbin\_4.5\ 虫洞(最短路练习)}\) - AcWing

代码

题解代码

模仿前先批处理一下会好很多。

#include<cstring>
#include<algorithm>
#include<queue>
#include <iostream>

using namespace std;
const int N = 6e3 + 10;
int n,m,k;

int h[N],e[N],ne[N],w[N],idx;

int st[N],cnt[N];
环计数组
int d[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

int spfa()
{
    memset(st,0,sizeof(st));
    memset(cnt,0,sizeof(cnt));
    memset(d,0,sizeof(d));
	多组输入要初始化。
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        q.push(i);
        st[i]=1;
    }
	所有点都可作为起点。
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=0;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            
            if(d[j]>d[t]+w[i])
            这里又变成取min了。
            应该是判正环还是负环的关键。
            取min判负环
            取max判正环
            {
                d[j]=d[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)
                    return 1;
                if(st[j]==0)
                {
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
    return 0;
}



int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    int T;
    cin >> T;
    while(T--)
    {
        memset(h,-1,sizeof(h));
        h和idx一定要在add前初始化
        idx=0;
        cin >> n >> m >> k;
        点，路，虫洞
        for(int i=1;i<=m;i++)//双向路径
        {
            int a,b,c;
            cin >> a >> b >> c;
            add(a,b,c),add(b,a,c);
        }

        for(int i=1;i<=k;i++)//单向虫洞
        {
            int a,b,c;
            cin >> a >> b >> c;
            add(a,b,-c);
            回溯所以负权。
        }

        if(spfa()==1)
            cout << "YES" << endl;
        else cout << "NO" << endl;


    }
    return 0;
}

模仿代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 6e3 + 10;
int n,m,k;
int ne[N],e[N],w[N],h[N],idx;
int st[N],cnt[N],d[N];
void add(int a,int b,int c){
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int spfa(){
	memset(st,0,sizeof st);
	memset(cnt,0,sizeof cnt);
	memset(d,0,sizeof d);
	queue<int> q;
	for(int i= 1;i <= n;i++){
		q.push(i);
		st[i] = 1;
		求最短路的话，去掉st会变慢。
		但求最短路的话会直接tle，所以还是不要去掉比较好。
	}
	while(q.size()){
		int t = q.front();
		q.pop();
		st[t] = 0;
		for(int i = h[t];i != -1;i = ne[i]){
			int j = e[i];
			if(d[j] > d[t] + w[i]){
				d[j] = d[t] + w[i];
				cnt[j] = cnt[t] + 1;
				if(cnt[j] >= n){
					return 1;
				}
				if(st[j] == 0){
					q.push(j);
					st[j] = 1;
				}
				
			}
		}
	}
	return 0;
	
}
int main(){
	int T;
	cin >> T;
	while(T--){
		memset(h,-1,sizeof h);
		idx = 0;
		cin >> n >> m >> k;
		for(int i = 1;i <= m;i++){
			int a,b,c;
			cin >> a >> b >> c;
			add(a,b,c),add(b,a,c);
		}
		for(int i = 1;i <= k;i++){
			int a,b,c;
			cin >> a >> b >> c;
			add(a,b,-c);
		}
		if(spfa()) cout << "YES" << endl;
		else cout << "NO" << endl;
		
	}
	return 0;
}

套路：无固定起点时的负环判断：

前提条件 任何点都可以做起点和终点

情景

现在农夫约翰希望能够从农场中的某片田地出发，经过一些路径和虫洞回到过去，并在他的出发时刻之前赶到他的出发地。

应对：

在spfa开始时，把所有点都作为起点处理一次。

例题6 Extended Traffic 判负环+求最短路

因为不理解负环所以在这题代码上花了点时间
负环详解 - 子谦。 - 博客园 (cnblogs.com)

代码

题解代码

// #include<bits/stdc++.h>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#define R register int
#define mm make_pair
#define inf 0x3f3f3f3f
using namespace std;
const int manx=1e3+5;
const int mamx=1e6+5;
struct node{
    int v,next,w;
}a[mamx];
int d[manx],head[manx],f[manx],ff[manx];
bool vis[manx];
int n,m,s,e,k=0;
void add(int u,int v,int w)
{
    a[++k].next=head[u];
    head[u]=k;
    a[k].v=v;
    a[k].w=w;
}
void spfa()
{
    memset(ff,0,sizeof(ff));
    memset(d,inf,sizeof(d));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    d[1]=0;
    ff[1]=1;
    q.push(1);
    while(q.size()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=a[i].next)
        {
            int v=a[i].v,w=a[i].w;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                if(!vis[v]&&ff[v]<=n){ //当ff[v]入队次数不大于n才进入if里面
                    ff[v]++;
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main()
{
    int o,oo=1;
    cin>>o;
    while(o--)
    {
        memset(head,0,sizeof(head));
        k=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&f[i]);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            int u,v,w;
            scanf("%d%d",&u,&v);
            w=int(pow(f[v]-f[u],3));
            add(u,v,w);
        }
        spfa();
        scanf("%d",&s);
        printf("Case %d:\n",oo++);
        while(s--)
        {
            scanf("%d",&e);
            if(ff[e]>n||d[e]<3||d[e]==inf) printf("?\n");
            else printf("%d\n",d[e]);
        }
    }
    return 0;
}

改造代码

// #include<bits/stdc++.h>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
using namespace std;
const int N=1e6+5;

int d[N],h[N],f[N],cnt[N];
bool st[N];
int n,m,s,ed,idx=0;
int w[N],ne[N],e[N];
void add(int a,int b,int c){
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
void spfa()
{
    memset(cnt,0,sizeof cnt);
    memset(d,0x3f,sizeof d);
    这题不仅要判负环，还要找最短路，所以dist要初始化成有意义的值。找最短路要初始化成0x3f，然后起点0;,
    memset(st,0,sizeof st);
    queue<int>q;
    q.push(1);
    d[1] = 0;
    不能初始化为-0x3f3f3f3f,因为第一次更新是要把d[j]变成w[i],但表达式是d[t] + w[i],所以起点要是0。
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=h[t];i != -1;i = ne[i])
        {
            int j=e[i];
            
            if(d[j]>d[t]+w[i]){
            更新最小值，所以要取min
                d[j]=d[t]+w[i];
                if(cnt[j] >= n) continue;
                为什么是> n，不理解.
                总算想明白了，脑瘫作者把起点cnt初始化为1了
                如果cnt[t] >= n,说明存在负环，此时负环中的点可以不断更新，不存在最小值，所以要停止更新。
                cnt[j] = cnt[t] + 1;
                if(!st[j]){ 
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
}
int main()
{
    int T,oo=1;
    cin>>T;
    while(T--)
    {
        memset(h,-1,sizeof(h));
        idx=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&f[i]);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d",&a,&b);
            c=pow(f[b]-f[a],3);
            add(a,b,c);
        }
        spfa();
        scanf("%d",&s);
        printf("Case %d:\n",oo++);
        while(s--)
        {
            scanf("%d",&ed);
            if(cnt[ed]>=n||d[ed]<3||d[ed]==0x3f3f3f3f) printf("?\n");
            无法到达或没有最小值
            else printf("%d\n",d[ed]);
        }
    }
    return 0;
}

卡壳点：

之前总结的负环d数组与起点初始化套路有点问题，如果要求最短路的话，dist和起点要照常初始化

套路：spfa判负环的写法与dist初始化

1.spfa判负环

有返回值：

cnt[j] >= n时return 1，函数最后return 0

无返回值：

cnt[j] >= n时continue;
最后再遍历cnt,看是否有>=n的来判断是否有

2.dist初始化

1）求最短路时，dist 0x3f3f3f3f + 起点0
2）求最长路时，dist -0x3f3f3f3f + 起点0
求最短路和最长路时应为dist更新方式是dist[t] + w[i],所以取起点0
但求最小边的最大值和最大边的最小值时
由于dist更新方式是max(dist[t],w[i])和min(dist[t],w[i])，所以起点要取成符合max与min的形式，即无穷大或无穷小。
1）求最小边的最大值 dist -0x3f3f3f3f + 起点0x3f3f3f3f
2）求最大边的最小值 dist 0x3f3f3f3f + 起点-0x3f3f3f3f

例题7：昂贵的聘礼 超级源点

代码

题解代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e4 + 10;
int m,n;
int level[N],st[N],d[N];
等级
int h[N],e[N],ne[N],w[N],idx;

void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}


int spfa(int l,int r)
{
    memset(d,0x3f,sizeof(d));
    memset(st,0,sizeof(st));

    queue<int> q;

    q.push(0);
    d[0]=0;
    st[0]=1;

    while(q.size())
    {
        int t=q.front();
        q.pop();

        st[t]=0;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];

            if(level[j]<l||level[j]>r)
                continue;
			通过设置lr边界来过滤。
            if(d[j]>d[t]+w[i])
            {
                d[j]=d[t]+w[i];
                if(st[j]==0)
                {
                    st[j]=1;
                    q.push(j);
                }
            }
        }
    }

    return d[1];
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    cin >> m >> n;

    memset(h,-1,sizeof(h));

    for(int i=1;i<=n;i++)
    {
        int price,cnt;
        cin >> price >> level[i] >> cnt;

        add(0,i,price);
        在0位置花price通向i
		虚拟源点与i建边。
        for(int j=1;j<=cnt;j++)
        {
            int id,cost;
            cin >> id >> cost;
            add(id,i,cost);
            在id位置花cost通向i
            降价部分，id与i建边。
        }
    }

    int res=0x3f3f3f3f;

    for(int i=level[1]-m;i<=level[1];i++)
        res=min(res,spfa(i,i+m));
        酋长不是等级最高的。

    cout << res << endl;

    return 0;
}

模仿代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e4 + 10;
int e[N],ne[N],w[N],h[N],idx;
int st[N],d[N],level[N];
void add(int a,int b,int c){
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int spfa(int l,int r){
	memset(st,0,sizeof st);
	memset(d,0x3f,sizeof d);
	
	queue <int> q;
	q.push(0);
	d[0] = 0;
	while(q.size()){
		int t = q.front();
		q.pop();
		st[t] = false;
		for(int i = h[t];~i;i = ne[i]){
			int j = e[i];
			if(level[j] < l || level [j] > r) continue;
			if(d[j] > d[t] + w[i]){
				d[j] = d[t] + w[i];
				if(!st[j]){
					st[j] = true;
					q.push(j);
				}
			}
		}
	}
	return d[1];
}
int main(){
	int n,m;
	cin >> m >> n;
	memset(h,-1,sizeof -1);
	for(int i =1;i <= n;i++){
		int price,cnt;
		cin >> price >> level[i] >> cnt;
		add(0,i,price);
		for(int j = 1;j <= cnt;j ++){
			int id;
			cin >> id >> price;
			add(id,i,price);
		}
		
	}
	int res = 0x3f3f3f3f;
	for(int i = level[1] - m;i <= level[1];i++){
		res = min(res,spfa(i,i+m));
	}
	cout << res <<endl;
	return 0;
}

卡壳点：

add函数里ne与e弄反了
双循环里把j写成了i

floyd 代码少：
练习：Tram
AcWing 4249. 电车 - AcWing
练习： Subway
AcWing 4248. 地铁 - AcWing

套路 超级源点

前提：

和反向建图解决的是同一类题，即求图上点到指定点的距离

情景

酋长要他用 1000010000 个金币作为聘礼才答应把女儿嫁给他。

探险家拿不出这么多金币，便请求酋长降低要求。

酋长说：”嗯，如果你能够替我弄到大祭司的皮袄，我可以只要 80008000 金币。如果你能够弄来他的水晶球，那么只要 50005000 金币就行了。”

探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。

探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。

不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。

探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。

抽象为从某个族人开始，然后一直交换到酋长处。

应对：

设置一个源点0，一般的做法是将各个点与超级源点之间建立一条权值为0的边。
然后再读入数据在各个点之间建边。

此题的点本身就有一个延伸出去的边（成员物品的price）即带权点
所以要把这些边读入，连到超级源点。

套路 带权点处理：

AcWing 903. 与y总不一样的思路 （思路简单代码简洁）：反向建图+链式前向星+堆优化版迪杰斯特拉+带点权判断 - AcWing

应对：

在不使用超级源点的情况下，要处理带权点的话，需要先用一个数组维护权值，然后在最短路跑出来后在函数的最后将权值加入d
原因：
如果在跑最短路时就将点权加入，可能原本要更新的d相对变大或变小，导致无法更新，或者原本不用更新的d被更新的情况

例题8：矩阵转换,邻接矩阵

情景

Xij 应满足以下条件：

  1. X12+X13+…+X1n=1
  2. 1的出度为1
  3. X1n+X2n+…Xn−1n=1
  4. n的入度为1
  5. 对于每个
  7. i（1<i<n），满足 ∑Xki(1≤k≤n)=∑Xij(1≤j≤n)
  8. 除了1和n，其他点的出度入度相等。

例如，当 n=4 时，需满足：

  1. X12+X13+X14=1
  2. X14+X24+X34=1
  3. X12+X22+X32+X42=X21+X22+X23+X24
  4. X13+X23+X33+X43=X31+X32+X33+X34
    1的出度为1，n的入度为0，其余点出入度相同。
    则转换为1到n的最短路，
    或者1出发，不经过n的环，
    n出发，不经过1的环。

代码

题解代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 310
int f[N][N];
邻接矩阵
int d[N],st[N];
int n;
void spfa(int stat)
{
    memset(d,0x3f,sizeof(d));
    memset(st,0,sizeof(st));

    queue<int> q;
    d[stat]=0;
    q.push(stat);
    while(q.size()>0)
    {
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=1;i<=n;i++)
            if(d[i]>d[t]+f[t][i])
            邻接表中，i是起点为t对应的边的编号，所以写成邻接矩阵形式是
            要说d[t]和起点为t，终点为i的边相加的目的是要更新哪个点的d的话，那必然是i了
            f[t][i]，
            {
                d[i]=d[t]+f[t][i];
                if(st[i]==0)
                {
                    st[i]=1;
                    q.push(i);
                }
            }
    }
}


int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&f[i][j]);

        spfa(1);
        int res=d[n];//1-n的最短路径
        //cout << res << endl;
        int res1=0x3f3f3f3f,res2=0x3f3f3f3f;
        for(int i=2;i<=n-1;i++)
            res1=min(res1,d[i]+f[i][1]);
		从点1出发经过除点n的任意点然后回到点1的环路;
		表示为1到i的最短路+f[i][1],起点为i，终点为1
		的边权。
        spfa(n);
        for(int i=2;i<=n-1;i++)
            res2=min(res2,d[i]+f[i][n]);
		从点n出发经过除点1的任意点然后回到点n的环路.
       printf("%d\n",min(res,res1+res2));
       最短路或最小二环距离和的min
    }
    return 0;
}

卡壳点：

标签：idx,int,短路,memset,st,sizeof,include
From： https://www.cnblogs.com/Kanna-STELLA/p/17450028.html

相关文章

  • Bellman-Ford算法——为什么要循环n-1次？图有n个点，又不能有回路，所以最短路径最多n-1边
    单源最短路径给定一个图,和一个源顶点src,找到从src到其它所有所有顶点的最短路径，图中可能含有负权值的边。Dijksra的算法是一个贪婪算法,时间复杂度是O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中不适用,Bellman-Ford适合这样的图。在网络路由中，该算法会被用作距......
  • spfa任意两点间最短路径
    #include<iostream>#include<queue>#include<string.h>usingnamespacestd;#defineINF0x3f3f3f3f;constintN=3000;intn,m;intg[N][N],dist[N];boolst[N];queue<int>q;voidspfa(intstart){st[start]=true;dist[s......
  • python dijkstra 最短路算法示意代码
     defdijkstra(graph,from_node,to_node):q,seen=[(0,from_node,[])],set()whileq:cost,node,path=heappop(q)seen.add(node)path=path+[node]ifnode==to_node:returncost,pathfora......
  • nyoj 307(最短路变形)
    解题思路：这道题和上一道题一样，也是最短路的变形，我之前的想法是二分答案，然后再dp去判断是否可以满足要求，但发现这样子的话会存在问题：因为一条路可能走多次，就无法保证其后效性。看了别人的思路：先以每个有宝藏的地方为起点，找到其到1号节点所符合题意的最大边max，表示最多可以从该节点运......
  • 第K短路（A*算法 启发式搜索算法）
    【启发式算法】定义函数h[x]=g[x]+f[x];其中g[x]是x结点的真实值，f[x]是x结点的估计剩余代价值，h[x]就是当前方案的总估计值。在BFS过程中，以最优价值优先遍历，可以减小时间复杂度，并简化问题。A*算法的优势就是，对当前结点做一个价值估计，取出堆中最优的结点进行下一次遍历。在求......
  • 设计可以求最短路径的图类
    类包括根据顶点数和边初始化的构造函数，添加边，求两点最短路径等函数1.邻接矩阵classGraph{private:vector<vector<int>>graph;public:Graph(intn,vector<vector<int>>&edges){graph.resize(n,vector<int>(n,INT_MAX/2));for(auto&......
  • POJ 1797 Heavy Transportation（迪杰斯特拉最短路变形）
    传送门题意分析：Hugo想要扩展他的公司，他有起重机要到目的地，到达目的地有很多条路径，但是，每一条路都有相应承重量，现在需要找出到达目的地的最大承重道路的承重质量。解题分析：首先，每一条路径的承重量取决于承重量最小的那条道路（短板效应），所以就是找所有路径的最小值，然后选择最小值最大的......
  • 最短路总结
    单源最短路Bellman-FordSPFADijkstraH-Dijkstra思路遍历全边，直到不变宽搜渐进，入队再更找最近点，更新邻点，找完不再用取负入队，大根堆找点，其余相同负边权能能否否判负环能能否否时间复杂度O(nm)O(km~nm)O(m+n^2)O(mlogn)适用于为什么不用SP......
  • Johnson 全源最短路
    全源最短路，换一种说法就是n个单源最短路，可以用n次Bellman-Ford或SPFA，非负边权还可以用Dijkstra，可是有负边权用前两个算法还是慢，如果我们能把负边权映射成非负边权的话，一切就都好办了这里我们引入一个虚拟结点，它和所有点的初始距离都是0，然后，我们求出来这个结点和其他店的最短路h，然......
  • Floyed 全源最短路
    全源最短路，顾名思义，就是任意两点之间的最短路floyed的思路就是每次选一个点k，如果k不在u和v路径上，就不改变，如果k在u和v的路径上，进行松弛操作d[u][v]=min(d[u][v],d[u][k]+d[k][v])例题洛谷B3647【模板】Floyd算法#include<iostream>#defineforup(i,l,r)for(inti=l;i<=r;......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99