C++ 最短路（spfa） 洛谷

 拉近距离

题目背景

我是源点，你是终点。我们之间有负权环。 ——小明

题目描述

在小明和小红的生活中，有 N 个关键的节点。有 M 个事件，记为一个三元组 (Si,Ti,Wi)，表示从节点 Si​ 有一个事件可以转移到 Ti​，事件的效果就是使他们之间的距离减少 Wi​。

这些节点构成了一个网络，其中节点 1 和 N 是特殊的，节点 1 代表小明，节点 N 代表小红，其他代表进展的阶段。所有事件可以自由选择是否进行，但每次只能进行当前节点邻接的。请你帮他们写一个程序，计算出他们之间可能的最短距离。

输入格式

第一行，两个正整数 N,M。

之后 M 行，每行 3 个空格隔开的整数 Si​,Ti​,Wi​。

输出格式

一行，一个整数表示他们之间可能的最短距离。如果这个距离可以无限缩小，输出Forever love。

#include<bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 1e5+10;
 
int n,m;
int suc = 1;
int dis[N],vis[N],cnt[N];//长度，标记，经历节点数 

vector<pair<int,int> > e[N];

int spfa(int A)
{
	for(int i=1;i<=n;i++)
	{
		dis[i] = 1e18;
		vis[i] = 0;
		cnt[i] = 0;
	}//清空上次操作 
	queue<int > q;
	q.push(A);
	dis[A] = 0;
	vis[A] = 1;
	while(q.size())
	{
		int now = q.front();
		q.pop();
		vis[now] = 0; 
		for(auto t:e[now])
		{
			int spot = t.first,w = t.second;
			if(dis[spot]>dis[now]-w)//距离减少 
			{
				dis[spot] = dis[now]-w;
				cnt[spot] = cnt[now]+1;//节点数增加 
				if(cnt[spot]>=n)//节点数大于总节点数 
				{
					suc = 0;//出现负环 
					return false;
				}
				if(vis[spot]==0)//没经历过 
				{
					vis[spot] = 1;//标记 
					q.push(spot);
				}
			}
		}
	}
	return true;
}

signed main()
{
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back({b,c});
	}
	spfa(1);
	int a = dis[n];//小明 -> 小红 经历最短距离 
	spfa(n);
	int b = dis[1];//小红 -> 小明 经历最短距离 
	if(suc==0) cout<<"Forever love";//出现负环，距离可以无限缩小 
	else cout<<min(a,b);//可能的最短距离 
    return 0;
}

邮递员送信

题目描述

有一个邮递员要送东西，邮局在节点 1。他总共要送 n−1样东西，其目的地分别是节点 2 到节点 n。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n−1 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数，n 和 m，表示城市的节点数量和道路数量。

第二行到第 (m+1)行，每行三个整数，u,v,w，表示从 u 到 v 有一条通过时间为 w 的道路。

输出格式

输出仅一行，包含一个整数，为最少需要的时间。

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

using namespace std;

const int M = 1e6+10;
queue<int> q;

int n,m,to,ta;
int u,v,w[M];
int dis1[M],dis2[M],vis[M];
int a1[M],b1[M],c1[M];
int a2[M],b2[M],c2[M];
void va1(int u,int v,int z) 
{
    a1[++to]=v;
	b1[to]=c1[u];
	c1[u]=to;
	w[to]=z;
}
void va2(int u,int v,int z) 
{
    a2[++ta]=v;
	b2[ta]=c2[u];
	c2[u]=ta;
	w[ta]=z;
}
void spfa1(int x) 
{
    for(int i = 1; i<=n; i++) 
	{
        dis1[i]=9999;
        vis[i]=0;
    }
    dis1[x]=0;
	vis[x]=1;
	q.push(x);
    while(q.size()) 
	{
        int now=q.front(); 
		q.pop(); 
		vis[now]=0;
        for(int i = c1[now]; i; i=b1[i])
		{
            int t=a1[i];
            if(dis1[t]>dis1[now]+w[i])
			{
                dis1[t]=dis1[now]+w[i];
                if(vis[t]==0) 
				{
					vis[t]=1;
					q.push(t);
				}
            }
        }
    }
}
void spfa2(int x) 
{
    for(int i = 1;i<=n;i++) 
	{
        dis2[i]=9999;
        vis[i]=0;
    }
    dis2[x]=0;
	vis[x]=1;
	q.push(x);
    while(q.size()) 
	{
        int now = q.front(); 
		q.pop(); 
		vis[now]=0;
        for(int i = c2[now]; i; i=b2[i])
		{
            int t=a2[i];
            if(dis2[t]>dis2[now]+w[i]) 
			{
                dis2[t]=dis2[now]+w[i];
                if(vis[t]==0) 
                {
                	vis[t]=1;
					q.push(t);
				}
				
            }
        }
    }
}
int main() 
{
    int sum1=0,sum2=0;
    cin>>n>>m;
    for(int i=1; i<=m;i++)
	{
        cin>>u>>v>>w[i];
        va1(u,v,w[i]);
        va2(v,u,w[i]);
    }
    spfa1(1);
    memset(vis,0,sizeof(vis));
    spfa2(1);
    for(int i=1; i<=n; i++) 
	{
        sum1+=dis1[i];
        sum2+=dis2[i];
    }
    cout<<sum1+sum2;
    return 0;
}

道路重建

题目描述

从前，在一个王国中，在 n 个城市间有 m 条道路连接，而且任意两个城市之间至多有一条道路直接相连。在经过一次严重的战争之后，有 d 条道路被破坏了。国王想要修复国家的道路系统，现在有两个重要城市 A 和 B 之间的交通中断，国王希望尽快的恢复两个城市之间的连接。你的任务就是修复一些道路使 A 与 B 之间的连接恢复，并要求修复的道路长度最小。

输入格式

输入文件第一行为一个整数 n (2<n≤100)，表示城市的个数。这些城市编号从 1 到 n。

第二行为一个整数 m (n−1≤m≤1/2n(n−1))，表示道路的数目。

接下来的 m 行，每行 3 个整数 i,j,k (1≤i,j≤n,i≠j,0<k≤100)，表示城市 i 与 j 之间有一条长为 k 的道路相连。

接下来一行为一个整数 d (1≤d≤m)，表示战后被破坏的道路的数目。在接下来的 d 行中，每行两个整数 i 和 j，表示城市 i 与 j 之间直接相连的道路被破坏。

最后一行为两个整数 A 和 B，代表需要恢复交通的两个重要城市。

输出格式

输出文件仅一个整数，表示恢复 A 与 B 间的交通需要修复的道路总长度的最小值。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define int long long 
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 
using namespace std;
 
const int N = 1e6+10;
 
int n,m,d,A,B;
int dis[N];
int vis[N]; 
map<pair<int,int>,int> mp;
vector<pair<int,int >> e[N];
 
void spfa()
{
	for(int i = 1;i<=n;i++) dis[i] = 1e18;
	queue<int > q;
	q.push(A);
	dis[A] = 0;
	vis[A] = 1;
	while(q.size())
	{
		int now = q.front();
		q.pop();
		vis[now] = 0;
		for(auto t:e[now])
		{
			int spot = t.first,w = 0;
			if(mp[{now,spot}]==1) w = t.second;
			if(dis[spot]>dis[now]+w)
			{
				dis[spot] = dis[now]+w;
				if(vis[spot]==0)
				{
					vis[spot] = 1;
					q.push(spot);
				}
			}
		}
	}
}
signed main()
{
	IOS;
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back({b,c});
		e[b].push_back({a,c});	
	}
	cin>>d;
	while(d--)
	{
		int a,b;
		cin>>a>>b;
		mp[{a,b}] = 1;
		mp[{b,a}] = 1;
	}
	cin>>A>>B;
	spfa();
	cout<<dis[B];
	return 0;
}