`

【floyd/要防重边】HDU 2923 Einbahnstrasse

阅读更多
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
1
1
分享到:
评论

相关推荐

    Floyd算法 Floyd算法

    wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 &gt;&gt; Matlab,Mathematica,maple,几何画板,word,sas,spss...使用方法技巧 我的收件箱 (0) 中国数学建模 → 数学...

    Floyd最短路径java实现

    在Java中实现Floyd算法,可以方便地处理具有负权边的图,只要图中不存在负权回路即可。 **算法流程** 1. 初始化:创建一个n×n的二维数组distance,其中distance[i][j]表示顶点i到顶点j的最短距离。对于非对角线...

    邻接多重表创建图,Floyd算法求最短路径

    在计算机科学领域,图是一种非常...实际应用这些概念时,我们需要将图的边数据转化为邻接多重表的结构,然后利用Floyd算法计算最短路径。通过理解和实践这些算法,我们可以有效地解决网络路由、交通路线优化等问题。

    Floyd算法_路径_floyd_matlab_

    **Floyd算法** Floyd算法,也称为Floyd-Warshall算法,是图论中用于查找有向图或无向图中所有顶点之间最短路径的一种经典算法。该算法由Robert Floyd在1962年提出,适用于解决多源最短路径问题,即寻找从图中的一个...

    floyd_路径规划_Floyd算法_dynamicdijkstra_

    Dijkstra算法不能处理负权重的边,而Floyd算法可以,这是两者的主要区别。此外,Dijkstra算法每次只处理一个源点,而Floyd处理所有顶点。 动态规划是Floyd算法的理论基础,它通过逐步构建最优解,将复杂问题转化为...

    floyd算法求最短路径

    Floyd算法适用于稠密图(边的数量接近于节点数量的平方),在稀疏图(边的数量远小于节点数量的平方)中,由于大量的无效比较,效率可能不如Dijkstra算法或Bellman-Ford算法。 需要注意的是,Floyd算法不能处理负权...

    Floyd算法.rar

    1. Dijkstra算法:适用于无负权边的最短路径问题,而Floyd可以处理负权边(但不保证找到最短路径)。 2. Bellman-Ford算法:同样能处理负权边,但时间复杂度为O(n*m),m为边的数量,对于稠密图,Floyd更优。 综上所...

    floyd求最短路径

    **Floyd算法详解** Floyd算法,又称为Floyd-Warshall算法,是解决图论问题中的一个经典算法,主要用于寻找图中所有顶点对之间的最短路径。它是由美国计算机科学家Robert W. Floyd在1962年提出的。这个算法基于动态...

    floyd最短路径算法

    **Floyd最短路径算法详解** Floyd-Warshall算法,通常称为Floyd算法,是图论中的一个著名算法,用于解决多源最短路径问题。这个算法由Robert Floyd在1962年提出,其核心思想是通过迭代的方式逐步完善最短路径信息,...

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    Floyd算法(可以输出最佳路径路线)

    Floyd算法,也被称为Floyd-Warshall算法,是图论中的一个重要算法,主要用于求解图中所有顶点之间的最短路径。这个算法由Robert Floyd和Stephen Warshall独立提出,因此得名。在计算机科学中,它常被用于解决网络...

    floyd_matlab_

    它通过一个二维数组(在这里可能是用“带权邻接矩阵.txt”文件表示)来存储图的边的权重,矩阵的每个元素表示一对顶点间的距离。初始时,这个矩阵通常包含了图的原始信息,即直接相连的顶点之间的距离。在每一轮迭代...

    最短路径算法 floyd

    Floyd-Warshall算法,通常简称为Floyd算法,是解决这一问题的有效方法之一。该算法由Robert Floyd和Stephen Warshall分别独立提出,因此得名。在本篇中,我们将深入探讨Floyd算法的基本原理、实现过程以及它在实际...

    算法-最短路径-Floyd算法

    Floyd算法的优点在于它能够处理负权边,只要这些边不形成负权环。对于含有负权环的图,Floyd算法可能会陷入无限循环,因为负权环会导致路径长度无限减小。在实际应用中,为了避免这种情况,通常会在算法开始前检查图...

    Floyd 算法 详细教程

    Floyd 算法适用于 APSP(All Pairs Shortest Paths),稠密图效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次 Dijkstra 算法。 Floyd 算法的优点是容易理解,可以算...

    基于MATLAB的Floyd算法

    基于MATLAB的Floyd算法,计算网络中任意结点间的最小距离!

    Floyd算法c语言实现

    在实际应用中,Floyd算法适用于处理含有负权边但无负权环的图,对于不含负权边的图,它与Dijkstra算法相比,更能在一次性计算所有顶点对的最短路径上体现优势。不过,对于大规模图,由于其较高的时间复杂度,可能会...

    FLoyd求最小环模板(有注释)(c++/c 语言)

    ### Floyd求最小环算法详解 #### 一、算法概述 Floyd算法是一种解决图论问题中的最短路径问题的经典算法,特别适用于寻找带权有向图中所有顶点对之间的最短路径。在某些特定场景下,我们可能还需要找出一个图中...

    Floyd最短路径算法C++实现

    Floyd算法适用于具有负权边但没有负权环的图。在实际应用中,它广泛应用于网络路由、交通规划、社交网络分析等领域,用于找出两个点之间最短的连接路径。 ### 4. 优化与限制 虽然Floyd算法的时间复杂度是O(n^3),...

    floyd算法C语言源程序

    **Floyd算法,也称为Floyd-Warshall算法,是一种著名的图论算法,主要用于寻找图中所有顶点之间的最短路径。在C语言中实现这一算法,可以为学习数据结构和算法的学生提供宝贵的经验。** Floyd算法的核心思想是基于...

Global site tag (gtag.js) - Google Analytics