航班Flight（SPFA+dp）- HDU 3499

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

4 0
Harbin Chengdu

800
-1

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

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

#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;
}