HDU - 3499 -(Dijkstra变形+枚举边)-白红宇

HDU - 3499 -(Dijkstra变形+枚举边)

阅读量：5009 次

发布时间：2019-06-12

本文共 3406 字，大约阅读时间需要 11 分钟。

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?

InputThere 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.

OutputOne 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 4Harbin Beijing 500Harbin Shanghai 1000Beijing Chengdu 600Shanghai Chengdu 400Harbin Chengdu4 0Harbin 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.   这个题的坑点在于建单向边，然后跑两边Dijkstra相当于处理前缀和后缀 然后枚举边就行了，还有初始化INF要大 可能爆longlong 代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define Inf 100000000000const int maxn=1e5+5;typedef long long ll;using namespace std;map
               
                mp;struct edge{ int u,v; ll w; int next;}Edge[10*maxn];struct node{ int pos; ll w; node(int x,int y) { pos=x; w=y; } bool friend operator < (node x,node y) { return x.w>y.w; }};int head[maxn];bool vis[maxn];int cnt;ll dis[maxn], dis2[maxn];int u[5*maxn],v[5*maxn];ll w[5*maxn];void add(int u,int v,int w){ Edge[cnt].u=u; Edge[cnt].v=v; Edge[cnt].w=w; Edge[cnt].next=head[u]; head[u]=cnt++;}void Dijkstra(int s){ dis[s]=0; priority_queue
                
                 q; q.push(node(s,0)); while(!q.empty()) { node now=q.top(); q.pop(); if(vis[now.pos])continue; vis[now.pos]=1; for(int i=head[now.pos];i!=-1;i=Edge[i].next) { if(dis[now.pos]+Edge[i].w
                 
                  q; q.push(node(s,0)); while(!q.empty()) { node now=q.top(); q.pop(); if(vis[now.pos])continue; vis[now.pos]=1; for(int i=head[now.pos];i!=-1;i=Edge[i].next) { if(dis2[now.pos]+Edge[i].w
                  
                   >n>>m) { int cc=1; cnt=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); for(int t=1;t<=100000;t++) { dis2[t]=Inf; dis[t]=Inf; } string st,ed; string uu,vv; mp.clear(); for(int t=0;t
                   
                    >uu>>vv>>w[t]; if(mp[uu]==0) { mp[uu]=cc++; } if(mp[vv]==0) { mp[vv]=cc++; } add(mp[uu],mp[vv],w[t]); u[t]=mp[uu]; v[t]=mp[vv]; //add(mp[v],mp[u],w); } cin>>st>>ed; if(st==ed) { puts("0"); continue; } if(mp[st]==0) { mp[st]=cc++; } //cout<
                    
                     <

转载于:https://www.cnblogs.com/Staceyacm/p/11296465.html

你可能感兴趣的文章