讲解

 模板

第1题     bellman-ford练习 查看测评数据信息

给定一个 n 个点 m 条边的有向图，图中可能存在重边但不存在自环， 边权可能为负数。请你求出从 1 号点到 n 号点最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。1≤n≤500 ，1≤m≤10000，任意边长的绝对值不超过 10000。
输入格式

 

第一行包含三个整数 n,m。

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

 
输出格式

 

输出一个整数，表示从 1 号点到 n 号点最短距离。如果不存在满足条件的路径，则输出 impossible。

 
输入/输出例子1

输入：

2 1

1 2 1

 

输出：

1

 
样例解释

无

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

const int N=1e4+5;
struct edge
{
	int u, v, w; //存边
}a[N];
int n, m, x, y, z;
int e=0, dis[N];
void bel(int s)
{
	memset(dis, 63, sizeof dis);
	dis[s]=0;
	for (int i=1; i<n; i++) //顶多n-1轮
	{
		for (int j=1; j<=e; j++) //遍历边
		{
			int u=a[j].u, v=a[j].v, w=a[j].w;
			if (dis[v]>dis[u]+w) //松弛
				dis[v]=dis[u]+w;
		}	
	}
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=1; i<=m; i++)
    {
    	scanf("%d%d%d", &x, &y, &z);
    	a[++e]={x, y, z}; //存边
	}
	bel(1);
	
	if (dis[n]==dis[0]) printf("impossible");
	else printf("%d", dis[n]);
    return 0;
}

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

给定一个 n 个点 m 条边的有向图，边权可能为负数。请判断该图是否存在负环，如果存在输出“Yes”,否则输出“No”。1≤n≤500 ，1≤m≤10000，任意边长的绝对值不超过 10000。
输入格式

 

第一行包含三个整数 n,m。

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

 
输出格式

 

存在负环输出“Yes”，否则输出“No”。

 
输入/输出例子1

输入：

2 1

1 2 1

 

输出：

No

 
样例解释

无

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

const int N=1e4+5;
struct edge
{
	int u, v, w;
}a[N];
int n, m, x, y, z;
int e=0, dis[N];
bool bel(int s)
{
	int flag=0;
	memset(dis, 63, sizeof dis);
	dis[s]=0;
	for (int i=1; i<=n; i++)
	{
		flag=0;
		for (int j=1; j<=e; j++)
		{
			int u=a[j].u, v=a[j].v, w=a[j].w;
			if (dis[v]>dis[u]+w)
				dis[v]=dis[u]+w, flag=1;
		}
		if (!flag) return false;
	}
	return true;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=1; i<=m; i++)
    {
    	scanf("%d%d%d", &x, &y, &z);
    	a[++e]={x, y, z};
	}
	
	if (bel(1)) printf("Yes");
	else printf("No");
    return 0;
}

思考题

https://www.cnblogs.com/didiao233/p/17991058