航班Flight(SPFA+dp)- HDU 3499

Recently, Shua Shua had a big quarrel with his GF. He is so upset that he decides to take a trip to some other city to avoid meeting her. He will travel only by air and he can go to any city if there exists a flight and it can help him reduce the total cost to the destination. There's a problem here: Shua Shua has a special credit card which can reduce half the price of a ticket ( i.e. 100 becomes 50, 99 becomes 49. The original and reduced price are both integers. ). But he can only use it once. He has no idea which flight he should choose to use the card to make the total cost least. Can you help him?

Input

There are no more than 10 test cases. Subsequent test cases are separated by a blank line. The first line of each test case contains two integers N and M ( 2 <= N <= 100,000 0 <= M <= 500,000 ), representing the number of cities and flights. Each of the following M lines contains "X Y D" representing a flight from city X to city Y with ticket price D ( 1 <= D <= 100,000 ). Notice that not all of the cities will appear in the list! The last line contains "S E" representing the start and end city. X, Y, S, E are all strings consisting of at most 10 alphanumeric characters.

Output

One line for each test case the least money Shua Shua have to pay. If it's impossible for him to finish the trip, just output -1.

Sample Input

4 4
Harbin Beijing 500
Harbin Shanghai 1000
Beijing Chengdu 600
Shanghai Chengdu 400
Harbin Chengdu

4 0
Harbin Chengdu

Sample Output

800
-1
概译:共有N个城市,M行里给出某市到另一个市(单向)的机票价格(这M行未必包含所有的N个城市),然后给出起始点和终点。这期间可以有一次机票打折机会,求解最小花费。如果到达不了,输出-1。

思路:显然的图题。如果没有打折这一条件的话就是有向图的最短路径,而打折条件是典型的、在每一步操作中可选可不选的条件类型,dp处理一下。也就是我们在求解最短路的过程中加上几条dp思想的语句来记录所需结果,此处最短路用的是spfa。另外注意一下这个题中,点的给出形式为字符串,我用的是STL中的map对其进行转化处理。
代码如下:

源代码:G++

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<vector>
#include<climits>
using namespace std;

typedef long long ll;
const long long inf = LLONG_MAX;

struct node
{
    int id, cost;
    node(int x, int y): id(x), cost(y) {}
};
int n, m, cnt; //点数、边数、在输入里出现过的城市数
ll dis[100005][2];//dp处理的距离
bool vis[100005];//spfa里负责记录是否在队列中
char ch1[15], ch2[15]; //城市1,城市2
//以下为最短路所需容器
map<string, int>mp;
vector<node>v[100005];
queue<int>q;

void spfa(int k)//求最短路
{
    for (int i = 1; i <= n; i++)
        dis[i][0] = dis[i][1] = inf;
    dis[k][0] = dis[k][1] = 0;
    //dis[i][0]代表到达i点时以前打过一次折的最小花费,即dis[城市2][0]就是结果,dis[i][1]是到达i点之前一直不打折的花费
    memset(vis, false, sizeof(vis));
    q.push(k);
    while (!q.empty())
    {
        int t = q.front(); q.pop();
        vis[t] = false;
        for (int i = 0; i < v[t].size(); i++)
        {
            node e = v[t][i];
            bool flag = false;
            if (dis[e.id][1] > dis[t][1] + e.cost) //常规操作,把dis[i][1]当成模板里的dis[i]就行……
            {
                flag = true;
                dis[e.id][1] = dis[t][1] + e.cost;
            }
            if (dis[e.id][0] > dis[t][0] + e.cost || dis[e.id][0] > dis[t][1] + e.cost / 2)
            {   //dp,之前打了折的花费加上这次的花费,与之前一直不打折这次打折的花费,取最小值为对于这个点的打过一次折以后的最小花费
                flag = true;
                dis[e.id][0] = min(dis[t][0] + e.cost, dis[t][1] + e.cost / 2);
            }
            if (flag && !vis[e.id]) //更新了花费且此点不在队列中时
            {
                vis[e.id] = true;
                q.push(e.id);
            }
        }
    }
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        //不要忘了各种清空
        cnt = 0;
        mp.clear();
        for (int i = 1; i <= n; i++)
            v[i].clear();
        //建图
        for (int i = 1; i <= m; i++)
        {
            int cost;//机票钱
            scanf("%s%s%d", ch1, ch2, &cost);
            //如果还没出现过这个城市,加进来,记录下来它的编号,简单起见第几个出现就是几了
            if (!mp[ch1]) mp[ch1] = ++cnt;
            if (!mp[ch2]) mp[ch2] = ++cnt;
            v[mp[ch1]].push_back(node(mp[ch2], cost)); //单向
        }
        scanf("%s%s", ch1, ch2); //起点终点
        if (!mp[ch1]) mp[ch1] = ++cnt;
        if (!mp[ch2]) mp[ch2] = ++cnt;
        spfa(mp[ch1]);//求解
        printf("%lld\n", dis[mp[ch2]][0] == inf ? -1 : dis[mp[ch2]][0]); //inf代表无法到达
    }
    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-06-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java 成神之路

高亮标红

30580
来自专栏数据分析

[数据分析工具] Pandas 功能介绍(二)

我们需要看第一季度的数据是怎样的,就需要使用条件过滤

25170
来自专栏CreateAMind

CS231n课程笔记翻译:Python Numpy教程

译者注:本文智能单元首发,翻译自斯坦福CS231n课程笔记Python Numpy Tutorial,由课程教师Andrej Karpathy授权进行翻译。本篇...

12330
来自专栏申龙斌的程序人生

参加steemit数学x程式大赛(第八回)

前一段时间参加了Steemit社区的两个活动,比如“接龙”创作大赛,五个人根据几张图片素材编出一篇小说,事先没有任何沟通,人员报名之后,顺序是随机指定的,我第一...

31460
来自专栏海天一树

NOIP 2011初赛普及组C/C++答案详解

3 C 8G = 8 * 1024 M 8 * 1024 / 2 = 4096张 注意,题目说的是“大约”,不要求精确。

14220
来自专栏数说工作室

统计师的Python日记【第七天:数据清洗(1)】

本文是【统计师的Python日记】第7天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型。 第2天学习了python的函数、...

566100
来自专栏数据结构与算法

洛谷P1731 [NOI1999]生日蛋糕(爆搜)

设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时,要求 R_i>R_{i+1}Ri​>Ri+1​ 且 H_i>H_{i+1}...

11010
来自专栏Crossin的编程教室

【每周一坑】谁是哪国人?

一道比较老套的题目: 在一个宾馆里住着六个不同国籍的人,他们分别来自美国、德国、英国、法国、俄罗斯和意大利。他们的名字叫 A、B、C、D、E、F。名字的顺序与...

27440
来自专栏Laoqi's Linux运维专列

python3–装饰器

42460
来自专栏Crossin的编程教室

【每周一坑】田忌赛马

本周的题目取自著名的历史典故:田忌赛马 背景资料如下 田忌经常与齐国众公子赛马,设重金赌注。田忌的上宾孙膑发现他们的马脚力都差不多,马分为上、中、下三等,于是对...

308100

扫码关注云+社区

领取腾讯云代金券