锐客网

  1. 首页 > 睿知 > it技术 > >

HDU - 3499 Flight （单源最短路+优惠问题）

IT知识问题单源最短路

历览千载书，时时见遗烈。这篇文章主要讲述HDU - 3499 Flight （单源最短路+优惠问题）相关的知识，希望能为你提供帮助。
题干：
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. Theres 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 its 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

【HDU - 3499 Flight （单源最短路+优惠问题）】Sample Output
800
-1

Hint
In the first sample, Shua Shua should use the card on the flight from
Beijing to Chengdu, making the route Harbin-> Beijing-> Chengdu have the
least total cost 800. In the second sample, theres no way for him to get to
Chengdu from Harbin, so -1 is needed.

题目大意：
      有一个有向图,你要从特定的城市A飞到城市B去.给你这个图的所有边(航班)信息.但是你手上有一张卡,可以使得某一趟航班的价格减半.现在的问题是你从A到B的最小费用是多少?
解题报告：
      首先要知道这条如果让一条原本是最短路径(假设总距离为x)上最长的边变成半价，最终求得的解不一定是最优的。因为假如现在有另外一条路径，假设该路径距离为x+1。且这条路径上只有5条边，4条长为1的边，但是1条长为x-3的边。如果我们让这条路径的x-3边变成半价是不是能得到更好的结果？
        明显必须从m条边中枚举那条半价的航班.假设这条半价的航班是i-> j的.那么我们必须知道从A到i的最短距离和从j到B的最短距离. 从A到i的最短距离可以通过求A的单源最短路径即可.从j(j有可能是任意点)到B的最短距离必须建立原图的反向图,然后求B到其他所有点的单源最短路径.(想想是不是)
        原题输入数据很多,需要用邻接表的dijkstra算法且距离要用long long保存.
AC代码：
#include< bits/stdc++.h>
#define ll long long
using namespace std;
//const int INF = 0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m;
int cnt1,cnt2,top;
map< string,int > mp;
ll dis1[100000 + 5],dis2[100000 + 5];
int head1[100000 + 5],head2[100000 + 5],cntt[100000 + 5];
bool vis[100000 + 5];
int st,ed;

struct Edge
int pos;
int to;
ll w;
int ne;
e[500000 + 5],E[500000 + 5];
struct point
int pos;
ll c;
point()//没有此构造函数不能写node t这样
point(int pos,int c):pos(pos),c(c)//可以写node(pos,cost)这样
bool operator < (const point & b) const
return c> b.c;

;

void add1(int u,int v,ll w)
e[cnt1].pos = u;
e[cnt1].to = v;
e[cnt1].w = w;
e[cnt1].ne = head1[u];
head1[u] = cnt1++;

void add2(int u,int v,ll w)
E[cnt2].pos = u;
E[cnt2].to = v;
E[cnt2].w = w;
E[cnt2].ne = head2[u];
head2[u] = cnt2++;

int Dijkstra1(int u,int v)
priority_queue< point> pq;
for(int i = 1; i< =n; i++) dis1[i] = INF;
memset(vis,0,sizeof(vis));
dis1[u] = 0;
point cur = point(u,0);
pq.push(cur);
while(!pq.empty())
point now = pq.top(); pq.pop();
vis[now.pos] = 1;
//if(now.pos == v) break;
for(int i = head1[now.pos]; i!=-1; i=e[i].ne)
if(dis1[e[i].to] > dis1[now.pos] + e[i].w )
dis1[e[i].to] = dis1[now.pos] + e[i].w;
pq.push(point(e[i].to,dis1[e[i].to] ) );



if(dis1[v] == INF) return -1;
else return dis1[v];

int Dijkstra2(int u,int v)
priority_queue< point> pq;
for(int i = 1; i< =n; i++) dis2[i] = INF;
memset(vis,0,sizeof(vis));
dis2[u] = 0;
point cur = point(u,0);
pq.push(

    推荐阅读


    上一篇：POJ-3259 Wormholes（判负环，spfa算法）

    下一篇：HDU - 3342Legal or Not（拓扑排序）