【HDU 3499】 Flight 最短路 分层图 Dijkstra堆优化 前向星

Problem Description

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

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, there’s no way for him to get to

Chengdu from Harbin, so -1 is needed.

Author

Edelweiss

Source

2010 ACM-ICPC Multi-University Training Contest（7）——Host by HIT

题意：有一个n个结点，m条边的有向图，可以对一条边进行边权减半的操作。问起点到终点的最短路

思路（分层图）：

对于图中边，可以做出k次选择（此题k=1）来改变边权。符合分层图的套路。构建一张平行层，这一层就相当于是原来图的复制品。然后原来的图（层）像新层移动的时候，如x -> y’，此边权即是边x->y的一半。按照这个思路，每次读入的时候多建立一条当前层像新层过渡的边，以及新层这两点之间的边。然后用这些点跑个Dijkstra即可。

可能会想，直接最短路把最长边减半不就行了吗。当然不行，WA点就在于，减半操作的加入，可能现在的“最短路”加进了一条新的边。如图：

原本最短路12+12=24，新最短路25/2=12。

最后，注意inf设置成比int大的值！

AC代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn = 1e6+5;
const ll inf=1e18;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') ch = getchar();while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };
const int V = 5e5, E=3e6;
ll d[V],cost[E];
ll n,m,a,b;
ll head[V],pnt[E],nxt[E],e=0;
ll vis[V];
map<string,ll> Map;
ll s,to;

void addedge(ll u,ll v,ll c)
{
    pnt[e]=v;       //当前以u为顶点，c为边长的，到v的一条边
    cost[e]=c;      //存入当前边权值
    nxt[e]=head[u];     //下一个其实是前一个
    head[u]=e++;        //当前边编号
}

ll Dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII> > q;
    d[s] = 0;
    q.push(mp(0LL,s));
    while(!q.empty())
    {
        ll x = q.top().se; q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i=head[x];i!=-1;i = nxt[i])
        {
            ll v = pnt[i];
            if(d[v]>d[x]+cost[i]&&!vis[v])
            {
                d[v] = d[x] + cost[i];
                q.push(mp(d[v], v));
            }
        }
    }
    return min(d[to],d[to+n])==inf?-1:min(d[to],d[to+n]);
}


int main()
{
   // FAST;
    while(~scanf("%lld%lld",&n,&m))
    {
        Map.clear();
        mem(vis,0);mem(head,-1);mem(cost,0); e = 0;
        rep(i,1,n<<2) d[i] = inf;
        ll idx = 1;
        rep(i,1,m)
        {
            ll x, y,z;
            string s1,s2;
            char s3[15],s4[15];
            scanf("%s",s3);scanf("%s",s4);
            s1 = s3 , s2 = s4;
            z = read();
            Map[s1] = x = Map[s1]?Map[s1]:idx++;
            Map[s2] = y = Map[s2]?Map[s2]:idx++;
            addedge(x,y,z);
            addedge(x,y+n,z/2);
            addedge(x+n,y+n,z);
        }
        string s1,s2; cin>>s1>>s2;
        s = Map[s1];
        to = Map[s2];
        if(Map[s1]&&Map[s2])
        {

            cout<< Dijkstra()<<'\n';
        }
        else cout<<-1<<'\n';
    }

    return 0;
}