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?

4 4

Harbin Beijing 500

Harbin Shanghai 1000

Beijing Chengdu 600

Shanghai Chengdu 400

Harbin Chengdu

4 0

Harbin Chengdu

800

-1

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. 

题意：ShuaShua要从一个城市到另一个城市，给出每两城市之间的花费（有向），ShuaShua可以有一次半价的机会，求最小花费。
思路：最短路径问题。开始想到求出最短路后选择其中最大的边/2，但其实错误，很容易举出反例：路径1：1 1 100 路径2：30 30 30 开始时102 90选择花费少的路径2，减半价后52 75路径1花费反而相对更少。
因此我们可以换一种思路，以起点和终点为单源分别求出到各点的最短路，然后枚举每一条边作为中间边，dis[u]+w(u,v)/2+diss[v]的最小值为解。

#include<stdio.h>

#include<string.h>

#include<vector>

#include<deque>

#include<map>

#include<string>

#define MAX 100005

#define MAXX 500005

#define INF 10000000000000000

using namespace std;

struct Node{

    int v,w;

}node;

vector <Node> edge[MAX],redge[MAX];

map<string,int> mp;

long long dis[MAX],diss[MAX],b[MAX],u[MAXX],v[MAXX],w[MAXX];

char s1[MAX],s2[MAX];

int n;

void spfa1(int k)

{

    int i;

    deque<int> q;

    for(i=;i<=n;i++){

        dis[i]=INF;

    }

    memset(b,,sizeof(b));

    b[k]=;

    dis[k]=;

    q.push_back(k);

    while(q.size()){

        int u=q.front();

        for(i=;i<edge[u].size();i++){

            int v=edge[u][i].v;

            long long w=edge[u][i].w;

            if(dis[v]>dis[u]+w){

                dis[v]=dis[u]+w;

                if(b[v]==){

                    b[v]=;

                    if(dis[v]>dis[u]) q.push_back(v);

                    else q.push_front(v);

                }

            }

        }

        b[u]=;

        q.pop_front();

    }

}

void spfa2(int k)

{

    int i;

    deque<int> q;

    for(i=;i<=n;i++){

        diss[i]=INF;

    }

    memset(b,,sizeof(b));

    b[k]=;

    diss[k]=;

    q.push_back(k);

    while(q.size()){

        int u=q.front();

        for(i=;i<redge[u].size();i++){

            int v=redge[u][i].v;

            long long w=redge[u][i].w;

            if(diss[v]>diss[u]+w){

                diss[v]=diss[u]+w;

                if(b[v]==){

                    b[v]=;

                    if(diss[v]>diss[u]) q.push_back(v);

                    else q.push_front(v);

                }

            }

        }

        b[u]=;

        q.pop_front();

    }

}

int main()

{

    int m,bg,ed,t,i,j;

    while(~scanf("%d%d",&n,&m)){

        t=;

        for(i=;i<=n;i++){

            edge[i].clear();

            redge[i].clear();

            mp.clear();

        }

        memset(u,,sizeof(u));

        memset(v,,sizeof(v));

        memset(w,,sizeof(w));

        for(i=;i<=m;i++){

            scanf(" %s%s%lld",s1,s2,&w[i]);

            if(!mp[s1]) mp[s1]=++t;

            if(!mp[s2]) mp[s2]=++t;

            u[i]=mp[s1];

            v[i]=mp[s2];

            node.v=mp[s2];

            node.w=w[i];

            edge[mp[s1]].push_back(node);

            node.v=mp[s1];

            redge[mp[s2]].push_back(node);

        }

        scanf(" %s%s",s1,s2);

        if(!mp[s1]) mp[s1]=++t;

        if(!mp[s2]) mp[s2]=++t;

        bg=mp[s1],ed=mp[s2];

        spfa1(bg);

        spfa2(ed);

        long long min=INF;

        for(i=;i<=m;i++){

            if(dis[u[i]]==INF||dis[v[i]]==INF) continue;

            if(dis[u[i]]+diss[v[i]]+w[i]/<min) min=dis[u[i]]+diss[v[i]]+w[i]/;

        }

        if(min==INF) printf("-1\n");

        else printf("%lld\n",min);

    }

    return ;

}