spfa
适用范围:存在负权边求最短路
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。
输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。
如果路径不存在,则输出 impossible。
数据范围
1≤n,m≤10^5,
图中涉及边长绝对值均不超过 10000。
输入样例:
3 3
1 2 5
2 3 -3
1 3 4
输出样例:
2
邻接矩阵
#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;
const int N = 1e4;
int a[N][N], d[N];
int n, m;
bool v[N];
queue<int> q;
int spfa()
{
memset(d, 0x3f3f3f3f, sizeof(d));
d[1] = 0;
q.push(1);
while (!q.empty())
{
int t = q.front();
q.pop();
for (int i = 1; i <= n; i++)
if (a[t][i] && d[i] > d[t] + a[t][i])
{
d[i] = d[t] + a[t][i];
q.push(i);
}
}
if (d[n] == 0x3f3f3f3f) return -1;
return d[n];
}
int main()
{
cin >> n >> m;
while (m--)
{
int x, y, z;
cin >> x >> y >> z;
a[x][y] = z;
}
if (spfa() == -1) cout << "impossible" << endl;
else cout << spfa() << endl;
}
邻接表
#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>
using namespace std;
const int N = 100100,M=100100;
int d[N];
int n, m;
bool v[N];
queue<int> q;
int head[N],to[M],w[M],nxt[M],idx=0; //head大小为点数,其他的大小为边数
void add(int a,int b,int c)
{
to[idx]=b;
w[idx]=c;
nxt[idx]=head[a];
head[a]=idx++;
}
int spfa()
{
memset(d, 0x3f, sizeof(d));
d[1] = 0;
q.push(1);
v[1]=true;
while (!q.empty())
{
int t = q.front();
q.pop();
v[t]=false;
for(int i=head[t];i!=-1;i=nxt[i])
{
int j=to[i];
if(d[j]>d[t]+w[i])
{
d[j]=d[t]+w[i];
if(!v[j])
{
q.push(j);
v[j]=true;
}
}
}
}
if (d[n] > 0x3f3f3f3f/2) return -1;
return d[n];
}
int main()
{
cin >> n >> m;
memset(head,-1,sizeof(head));
while (m -- )
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
}
if (spfa() == -1) cout << "impossible" << endl;
else cout << spfa() << endl;
}
Floyd
适用条件:求多源最短路,即求任意两个点之间的最短路问题
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。
再给定 k 个询问,每个询问包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短距离,如果路径不存在,则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。
接下来 k 行,每行包含两个整数 x,y,表示询问点 x 到点 y 的最短距离。
输出格式
共 k 行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出 impossible。
数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。
输入样例:
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例:
impossible
1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300;
int a[N][N];
int n,m,k;
int floyd()
{
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
}
}
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j) a[i][j]=0;
else a[i][j]=0x3f3f3f3f;
}
}
while (m -- )
{
int x,y,z;
cin>>x>>y>>z;
a[x][y]=min(a[x][y],z);
}
floyd();
while(k--)
{
int x,y;
cin>>x>>y;
if(a[x][y]>0x3f3f3f3f/2) cout<<"impossible"<<endl;
else cout<<a[x][y]<<endl;
}
}
Q.E.D.