算法基础

模板题

第1题     spfa最短路练习 查看测评数据信息

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。数据保证不存在负权回路。1≤n,m≤100000 ,图中涉及边长绝对值均不超过 10000。
输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

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

如果路径不存在，则输出 impossible。

输入/输出例子1

输入：

3 3

1 2 5

2 3 -3

1 3 4

输出：

2

样例解释

无

#include <bits/stdc++.h>
using namespace std;
 
const int N=1e5+5;
struct edge
{
	int v, w;
};
int n, m, u1, v1, w1, dis[N], vis[N];
vector<edge> a[N];
queue<int> q;
void spfa(int s) //很像bfs
{
	memset(dis, 63, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s]=0;
	q.push(s);
	
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		
		for (int i=0; i<a[u].size(); i++) //扩散到的点
		{
			int v=a[u][i].v, w=a[u][i].w;
			if (dis[v]>dis[u]+w) //松弛
			{
				dis[v]=dis[u]+w;
				if (!vis[v]) q.push(v), vis[v]=1; //防止重复入队
			}
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		a[u1].push_back({v1, w1});
	}    
	spfa(1);
	
	if (dis[n]==dis[0]) printf("impossible");
	else printf("%d", dis[n]);
    return 0;
}

第2题     spfa判断负环 查看测评数据信息

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你判断图中是否存在负权回路。1≤n≤2000 ，1≤m≤100000，图中涉及边长绝对值均不超过 10000。
输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

如果图中存在负权回路，则输出 Yes，否则输出 No。

输入/输出例子1

输入：

3 3

1 2 -1

2 3 4

3 1 -4

输出：

Yes

样例解释

无

#include <bits/stdc++.h>
using namespace std;
 
const int N=1e5+5;
struct edge
{
	int v, w;
};
int n, m, u1, v1, w1, dis[N], vis[N], cnt[N];
vector<edge> a[N];
queue<int> q;
bool spfa(int s)
{
	memset(dis, 63, sizeof dis);
	memset(vis, 0, sizeof vis);
	memset(cnt, 0, sizeof cnt);
	dis[s]=0;
	cnt[s]=1;
	q.push(s);
	
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		
		for (int i=0; i<a[u].size(); i++)
		{
			int v=a[u][i].v, w=a[u][i].w;
			if (dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if (!vis[v]) 
				{
					q.push(v), vis[v]=1, cnt[v]++;
					if (cnt[v]>n) //入队超过n次，必定有负环
						return true;
				}
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		a[u1].push_back({v1, w1});
	}    
	if (spfa(1)) printf("Yes");
	else printf("No");
	
    return 0;
}