http://acm.hdu.edu.cn/showproblem.php?pid=2923
一开始题意理解错了……英语太水了
要从公司开始按所给顺序把车拉回来,是一辆一辆车拖回来……这是常识……我竟然想着最后一堆车拖回来
Sample Input
4 2 5
NewTroy Midvale Metrodale
NewTroy <-20-> Midvale
Midvale --50-> Bakerline
NewTroy <-5-- Bakerline
Metrodale <-30-> NewTroy
Metrodale --5-> Bakerline
0 0 0
Sample Output
1. 80
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define inf 0x3fffffff
#define M 1005
map<string, int> m;
int n, dist[M][M], ind[M];
void init ()
{
m.clear();
int i, j;
for (i = 1; i <= n; i++)
for (j = i + 1; j <= n; j++)
dist[i][j] = dist[j][i] = inf;
}
void floyd ()
{
int i, j, k;
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
int main()
{
int c, r, i, key, w, res, cc = 1, len, k, j, u, v;
bool flag, mark;
char s1[15], s2[15], s[15], tp[15];
while (scanf ("%d%d%d", &n, &c, &r), (n||c||r))
{
key = 1;
init ();
for (i = 0; i <= c; i++)
{
scanf ("%s", s);
string p(s);
if (m[p] == 0)
m[p] = key++; //将字符串p映射为key【编号】
ind[i] = m[p];
}
for (i = 0; i < r; i++)
{
flag = mark = false;
scanf ("%s%s%s", s1, s, s2);
string p1(s1);
if (m[p1] == 0)
m[p1] = key++;
u = m[p1];
string p2(s2);
if (m[p2] == 0)
m[p2] = key++;
v = m[p2];
len = strlen(s);
k = 0;
for (j = 0; j < len; j++)
{
if (s[j] == '<') flag = true;
if (s[j] == '>') mark = true;
if (s[j] >= '0' && s[j] <= '9')
tp[k++] = s[j]; //tp读取箭头中间的数字
}
tp[k] = 0;
sscanf (tp, "%d", &w); //tp转化成int存放到w
if (flag && w < dist[v][u]) dist[v][u] = w;
if (mark && w < dist[u][v]) dist[u][v] = w;
//记得判断重边【w < dist[v][u]】,wa了无数次
}
floyd();
res = 0;
for (i = 1; i <= c; i++)
res += (dist[1][ind[i]] + dist[ind[i]][1]);
//先从1去那里,再把车拉回1,根据题意,是按顺序一个一个拖回来
printf ("%d. %d\n", cc++, res);
}
return 0;
}
- 大小: 12.6 KB
分享到:
相关推荐
wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> Matlab,Mathematica,maple,几何画板,word,sas,spss...使用方法技巧 我的收件箱 (0) 中国数学建模 → 数学...
基于MATLAB的Floyd算法,计算网络中任意结点间的最小距离!
Floyd最短路径算法的java实现,文件内附测试用例拓扑。
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
Floyd算法直接使用二维数组求出所有顶点到所有顶点的最短路径。 D代表顶点到顶点的最短路径权值和的矩阵。 P代表对应顶点的最小路径的前驱矩阵。 以下程序在DEV C++中调试运行通过。 #include <stdio> #define ...
邻接多重表创建图,Floyd算法求最短路径
利用误差扩散算法中的Floyd-Steinberg抖动算法来对图像进行二值化处理,从而方便图像调频加网输出Floyd-Steinberg
Floyd算法 详细介绍了Floyd算法的应用
Floyd算法适用于APSP(All Pairs Shortest Paths),是一种动态规划算法,稠密图效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法。
最短路径算法 floyd
本代码是floyd算法的通用matlab程序,代码写的十分经典,是数模比赛的利器
使用c++,调用mpi进行floyd并向计算
floyd算法m文件
求最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
使用Floyd算法,求解点对之间的最短距离。图结构使用邻接矩阵存储。
matlab实现的floyd算法,matlab实现的floyd算法
floyd算法,C语言编写的程序,适合学生作业。非常专业
更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd...
Floyd算法.doc
floyd最短路算法 最短路程序