題干：

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 Chengdu4 0 Harbin Chengdu

Sample Output

800 -1

Hint

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

題目大意：

? ? ?有一個有向圖,你要從特定的城市A飛到城市B去.給你這個圖的所有邊(航班)信息.但是你手上有一張卡,可以使得某一趟航班的價格減半.現(xiàn)在的問題是你從A到B的最小費用是多少?

解題報告：

? ? ?首先要知道這條如果讓一條原本是最短路徑(假設(shè)總距離為x)上最長的邊變成半價，最終求得的解不一定是最優(yōu)的。因為假如現(xiàn)在有另外一條路徑，假設(shè)該路徑距離為x+1。且這條路徑上只有5條邊，4條長為1的邊，但是1條長為x-3的邊。如果我們讓這條路徑的x-3邊變成半價是不是能得到更好的結(jié)果？

? ? ? ? 明顯必須從m條邊中枚舉那條半價的航班.假設(shè)這條半價的航班是i->j的.那么我們必須知道從A到i的最短距離和從j到B的最短距離. 從A到i的最短距離可以通過求A的單源最短路徑即可.從j(j有可能是任意點)到B的最短距離必須建立原圖的反向圖,然后求B到其他所有點的單源最短路徑.(想想是不是)

? ? ? ? 原題輸入數(shù)據(jù)很多,需要用鄰接表的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(){}//沒有此構(gòu)造函數(shù)不能寫 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(cur);while(!pq.empty()) {point now = pq.top();pq.pop();vis[now.pos] = 1; // if(now.pos == v) break;for(int i = head2[now.pos]; i!=-1; i=E[i].ne) {if( dis2[E[i].to] > dis2[now.pos] + E[i].w ) {dis2[E[i].to] = dis2[now.pos] + E[i].w;pq.push(point(E[i].to,dis2[E[i].to] ) ); } } } if(dis2[v] == INF) return -1;else return dis2[v]; } int main() {char tmp1[1000],tmp2[1000];ll w;ll tmp;//n個點，m條邊。 while(~scanf("%d%d",&n,&m) ) {top = 0;cnt1 = 0;cnt2 = 0;memset(head1,-1,sizeof(head1));memset(head2,-1,sizeof(head2));mp.clear();for(int i = 1; i<=m; i++) {scanf("%s %s %lld",tmp1,tmp2,&w);if(mp.find(tmp1) == mp.end() ) mp[tmp1] = ++top;if(mp.find(tmp2) == mp.end() ) mp[tmp2] = ++top;add1(mp[tmp1],mp[tmp2],w);add2(mp[tmp2],mp[tmp1],w);}scanf("%s%s",tmp1,tmp2);if(m == 0) {printf("-1\n");continue;}st = mp[tmp1],ed = mp[tmp2];ll minn = INF;tmp = Dijkstra1(st,ed);if(tmp == -1) {printf("-1\n");continue;} // for(int i = 1; i<=n; i++) { // printf("%lld ",dis1[i]); // }tmp = Dijkstra2(ed,st);if(tmp == -1) {printf("-1\n");continue;} // printf("\n************\n"); // for(int i = 1; i<=n; i++) { // printf("%lld ",dis2[i]); // } // printf("\n");for(int i=0;i<m;i++){int u=e[i].pos;int v=e[i].to;ll w=e[i].w; if(minn>dis1[u]+dis2[v]+(w/2))minn=dis1[u]+dis2[v]+(w/2); // cout<<u<<" "<<v<<" "<<w<<" "<<minn<<endl;} // }printf("%lld\n",minn);}return 0 ; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【HDU - 3499】 Flight （单源最短路+优惠问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。