解析

模板

第1题     floyd练习 查看测评数据信息

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。数据保证图中不存在负权回路。1≤n≤200 ，1≤k≤n，1≤m≤20000。图中涉及边长绝对值均不超过 10000。


输入格式

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

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

输出格式

共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

输入/输出例子1

输入：

3 3 2

1 2 1

2 3 2

1 3 1

2 1

1 3

输出：

impossible

1

样例解释

无

#include <bits/stdc++.h>
using namespace std;
 
const int N=205;
int n, m, k, u1, v1, w1, dis[N][N];
void flo()
{
	for (int k=1; k<=n; k++)
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
                dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j]);
}
int main()
{
	memset(dis, 63, sizeof dis);
	scanf("%d%d%d", &n, &m, &k);
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		dis[u1][v1]=min(dis[u1][v1], w1); //防止重边
		dis[u1][u1]=0, dis[v1][v1]=0;
	}
	flo();
	/*for (int i=1; i<=n; i++)
	
		for (int j=1; j<=n; j++)
			cout<<dis[i][j]<<" ";
		cout<<endl;
	}*/
	while (k--)
	{
		scanf("%d%d", &u1, &v1);
		if (dis[u1][v1]>dis[0][0]/2) printf("impossible\n"); //有负权边，但是怎么样多少负数相加也不可能超过初值的一半，详解看下面
		else printf("%d\n", dis[u1][v1]);
	} 
    return 0;
}

 为什么是“dis[u1][v1]>dis[0][0]/2”

第2题     牛奶加工站 查看测评数据信息

牛奶生意正红红火火！农夫约翰的牛奶加工厂内有 N 个加工站，编号为 1…N，以及 N−1 条通道，每条连接某两个加工站。（通道建设很昂贵，所以约翰选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。为了创新和提升效率，约翰在每条通道上安装了传送带。不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。然而，约翰认为事情可能还不算完全失败，只要至少还存在一个加工站 i 满足从其他每个加工站出发都可以到达加工站 i。注意从其他任意一个加工站 j 前往加工站 i 可能会经过 i 和 j 之间的一些中间站点。请帮助约翰求出是否存在这样的加工站 i。

1<=N<=100


输入格式

输入的第一行包含一个整数 N，为加工站的数量。以下 N−1行每行包含两个空格分隔的整数 ai 和 bi，满足 1≤ai,bi≤N 以及 ai≠bi。这表示有一条从加工站 ai 向加工站 bi 移动的传送带，仅允许沿从 ai 到 bi 的方向移动。

输出格式

如果存在加工站 i 满足可以从任意其他加工站出发都可以到达加工站 i，输出最小的满足条件的 i。否则，输出 −1。

输入/输出例子1

输入：

3

1 2

3 2

输出：

2

大样例压缩包

点击下载
样例解释

无

#include <bits/stdc++.h>
using namespace std;
 
const int N=205;
int n, u1, v1, w1, dis[N][N];
void flo()
{
	for (int k=1; k<=n; k++)
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j]);
}
int main()
{
	memset(dis, 63, sizeof dis);
	scanf("%d", &n);
	for (int i=1; i<n; i++)
	{
		scanf("%d%d", &u1, &v1);
		w1=1;
		dis[u1][v1]=min(dis[u1][v1], w1);
		dis[u1][u1]=0, dis[v1][v1]=0;
	}
	flo();
	
	for (int i=1; i<=n; i++)
	{
		int flag=0;
		for (int j=1; j<=n; j++)
			if (dis[j][i]==dis[0][0]) 
			{
				flag=1;
				break;
			}
		if (!flag)
		{
			printf("%d", i);
			return 0;
		}
	}
	printf("-1");
    return 0;
}

思考题

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