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 longusing 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;
}