欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 3631 Shortest Path

程序员文章站 2022-07-10 17:06:54
...

传送门

floyd插点。(看起来难实际很简单)
给你一个有向多重图(就是可能会有重边和自环,对应简单图),会标记一些点,然后再询问给定两点的最短路,要求该最短路上经过的点都是被标记过的(必然包括起点终点)。

权值都为正,看样例,发现当起点终点相同时最短路必然是0(当然这个点得标记过才行)。其实这题就是把floyd的第一层循环k拆成在线处理了,给一个标记点,然后就运行一遍以这个标记点为k值的2/3版的floyd就完事了,当问最短路的时候都是建立在这句之前的操作上,那么就直接输出当前结果就ok了。

理解floyd的动态规划本质,所谓k就是个中介点,而且不用关心k的循环次序。每次输出的最短路绝对不会经过没标记的点,因为之前没拿那些点当中介点。

这道题输出也给你玩个文字游戏,要求每相邻两个case之间才能有空行,最后不能有。


#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

const int INF = 1e9;
const int MAX = 300 + 5;
int N, M, Q;

int g[MAX][MAX];
bool mark[MAX];

void init()
{
	for (int i = 0; i < N; i++)
	{
		g[i][i] = 0;                                    // 
		for (int j = i + 1; j < N; j++)                 // 这样就比较简洁
		{
			g[i][j] = g[j][i] = INF;
		}
	}
	memset(mark, 0, sizeof mark);
}

void floyd_k(int k)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (g[i][k] != INF && g[k][j] != INF && g[i][k] + g[k][j] < g[i][j])
			{
				g[i][j] = g[i][k] + g[k][j];
			}
		}
	}
}

int main()
{
	int a, b, c;
	for (int cnt = 1; ~scanf("%d%d%d", &N, &M, &Q); cnt++)
	{
		if (!N && !M && !Q) break;
		init();
		for (int i = 0; i < M; i++)
		{
			scanf("%d%d%d", &a, &b, &c);
			g[a][b] = min(g[a][b], c);
		}

		if (cnt != 1) printf("\n");
		printf("Case %d:\n", cnt);
		for (; Q--;)
		{
			scanf("%d", &a);
			if (a == 0)
			{
				scanf("%d", &b);
				if (mark[b]) printf("ERROR! At point %d\n", b);
				else
				{
					mark[b] = true;
					floyd_k(b);
				}
			}
			else
			{
				scanf("%d%d", &b, &c);
				if (!mark[b] || !mark[c]) printf("ERROR! At path %d to %d\n", b, c);
				else if (g[b][c] == INF) printf("No such path\n");
				else printf("%d\n", g[b][c]);
			}
		}
		//printf("\n");
	}

	return 0;
}