航班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。

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

216 篇文章34 人订阅

0 条评论

相关文章

30580

25170

12330

31460

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

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

14220

566100

11010

27440

42460