P1529 回家 Bessie Come Home网页链接P1529 回家 Bessie Come Home题目描述现在是晚餐时间而母牛们在外面分散的牧场中。Farmer John 按响了电铃所以她们开始向谷仓走去。 你的工作是要指出哪只母牛会最先到达谷仓在给出的测试数据中总会有且只有一只最快的母牛。在挤奶的时候晚餐前每只母牛都在她自己的牧场上一些牧场上可能没有母牛。每个牧场由一条条道路和一个或多个牧场连接可能包括自己。有时两个牧场可能是字母相同的之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此所有的母牛最后都能到达谷仓并且母牛总是走最短的路径。当然母牛能向着任意一方向前进并且她们以相同的速度前进。牧场被标记为a … z \texttt{a} \ldots \texttt{z}a…z和A … Y \texttt{A} \ldots \texttt{Y}A…Y在用大写字母表示的牧场中有一只母牛小写字母中则没有。 谷仓的标记是Z \texttt{Z}Z注意没有母牛在谷仓中。注意m \texttt{m}m和M \texttt{M}M不是同一个牧场。输入格式第一行一个整数P PP1 ≤ P ≤ 10 4 1\leq P \leq 10^41≤P≤104表示连接牧场谷仓的道路的数目。接下来P PP行每行用空格分开的两个字母和一个正整数被道路连接牧场的标号和道路的长度道路长度均不超过10 3 10^3103。输出格式单独的一行包含二个项目最先到达谷仓的母牛所在的牧场的标号和这只母牛走过的路径的长度。输入输出样例 #1输入 #15 A d 6 B d 3 C e 9 d Z 8 e Z 3输出 #1B 11说明/提示翻译来自 NOCOWUSACO 2.4解题思路本题是多源最短路问题母牛分布在部分大写字母标记的牧场谷仓位于Z。目标是在所有有牛的牧场中找到到达Z最短路径长度及对应的牧场。由于节点数极少最多 52 个牧场采用 Floyd-Warshall 全源最短路直接求解。1. 问题建模节点与边牧场用字母A~Z和a~z标记共52 5252个节点。谷仓是Z。道路是无向边有长度两个牧场之间可能有多条道路取最小值。有牛标记大写的A~Y牧场中可能有一只母牛题目保证至少一只且只有一只最快。Z是谷仓无牛。目标在所有p[i]1即有牛的大写字母节点中找出到Z最短路径的节点及其距离。2. 算法实现初始化邻接矩阵a [ 256 ] [ 256 ] a[256][256]a[256][256]存储任意两点间的最短距离对角线为0 00其余初始化为一个极大值10 8 10^8108。读入与建图读取边数n nn。每行读取两个字母和一个正整数长度。若字母是大写标记p[字母]1。更新a [ A ] [ B ] a[A][B]a[A][B]和a [ B ] [ A ] a[B][A]a[B][A]为当前存储值与输入长度的较小值处理重边。Floyd-Warshall 全源最短路三层循环中间节点k kk起点i ii终点j jj覆盖A到z的所有字母。松弛操作若a [ i ] [ j ] a [ i ] [ k ] a [ k ] [ j ] a[i][j] a[i][k] a[k][j]a[i][j]a[i][k]a[k][j]则更新。寻找最优母牛遍历大写字母A到Y如果该节点有牛且a [ i ] [ ′ Z ′ ] a[i][Z]a[i][′Z′]小于当前最小值更新最小距离m mm和牧场标号h e hehe。输出输出牧场标号和最短距离。3. 复杂度分析时间复杂度Floyd-Warshall 的节点数V 52 V52V52复杂度O ( V 3 ) ≈ 1.4 × 10 5 O(V^3) \approx 1.4 \times 10^5O(V3)≈1.4×105对于P ≤ 10 4 P \le 10^4P≤104条边完全可行。空间复杂度O ( V 2 ) O(V^2)O(V2)邻接矩阵仅需256 × 256 256 \times 256256×256个long long空间极小。总结将字母牧场映射为图的节点无向边带权用 Floyd 算法求出所有牧场间最短路径再遍历有牛的大写牧场取到Z的最小距离者即为答案。注意处理重边取最小值区分大小写节点即可。代码简要说明全局数组a[256][256]邻接矩阵存储最短距离。p[256]标记大写字母牧场是否有牛。初始化与输入所有i≠j的a [ i ] [ j ] a[i][j]a[i][j]初始化为10 8 10^8108。用scanf读取边更新矩阵并标记有牛的节点。Floyd 核心三层循环遍历所有字母更新a[i][j] min(a[i][j], a[i][k]a[k][j])。结果查找与输出遍历A~Y找到有牛且距离Z最短的节点输出字符和距离。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll a[256][256]{0};ll p[256]{0};ll n,i,j,k;charA,B;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld\n,n);for(iA;iz;i)for(jA;jz;j)if(i!j)a[i][j]100000000;for(i1;in;i){ll haha;scanf(%c %c %lld\n,A,B,haha);if(AAAZ)p[A]1;if(BABZ)p[B]1;a[A][B]min(a[A][B],haha);a[B][A]min(a[A][B],a[B][A]);}for(kA;kz;k)for(iA;iz;i)for(jA;jz;j)if(a[i][j]a[i][k]a[k][j])a[i][j]a[i][k]a[k][j];ll m100000000;charhe;for(iA;iY;i)if((p[i]1)(a[i][Z]m)){ma[i][Z];he(char)i;}couthe mendl;return0;}
