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
题目大意：
给定一个有向图，你可以将某一条边的权值减半。 求从起点ss至终点ee的最短路。
核心思想：
正向建图，以ss为起点跑一遍Dijkstra，ss至各点的最短距离存在td数组中。 反向建图，以ee为起点跑一遍Dijkstra，ee至各点的最短距离存在dis数组中。 枚举每一条边lu[i]，将其权值lu[i].v减半，设此边起点为x，终点为y。这种情况对应的ans为td[x]+lu[i].v/2+dis[y]。求出所有ans，取最优值。
代码如下：
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
#define inf 1e17
using namespace std
;
typedef long long ll
;
const int N
=1e5+20,M
=5e5+20;
string s
,t
;
map
<string
,int>mp
;
int head
[N
],cnt
,cd
,cl
;
ll dis
[N
],td
[N
];
bool vis
[N
];
struct tnode
{
int x
,y
;
ll v
;
tnode()
{
}
tnode(int xx
,int yy
,ll vv
)
{
x
=xx
;
y
=yy
;
v
=vv
;
}
}lu
[M
];
struct node
{
int y
,ne
;
ll v
;
}side
[M
];
struct Node
{
int y
;
ll v
;
Node()
{
}
Node(int yy
,ll vv
)
{
y
=yy
;
v
=vv
;
}
bool operator
<(const Node oth
)const
{
return v
>oth
.v
;
}
};
void add(int x
,int y
,ll v
)
{
side
[cnt
].y
=y
;
side
[cnt
].v
=v
;
side
[cnt
].ne
=head
[x
];
head
[x
]=cnt
++;
return;
}
void dij(int st
)
{
for(int i
=0; i
<N
; i
++)
{
dis
[i
]=inf
;
vis
[i
]=0;
}
dis
[st
]=0;
priority_queue
<Node
>q
;
q
.push(Node(st
,0));
while(!q
.empty())
{
int te
=q
.top().y
;
q
.pop();
if(vis
[te
])continue;
vis
[te
]=1;
for(int i
=head
[te
]; i
!=-1; i
=side
[i
].ne
)
{
int ty
=side
[i
].y
;
ll tv
=side
[i
].v
;
if(dis
[ty
]>dis
[te
]+tv
)
{
dis
[ty
]=dis
[te
]+tv
;
q
.push(Node(ty
,dis
[ty
]));
}
}
}
return;
}
void init()
{
mp
.clear();
cd
=1;
return;
}
int main()
{
int n
,m
,x
,y
,ss
,ee
;
ll v
;
while(scanf("%d%d",&n
,&m
)!=EOF)
{
init();
cl
=0;
for(int i
=0;i
<m
;i
++)
{
cin
>>s
>>t
>>v
;
if(!mp
[s
])
{
mp
[s
]=cd
;
x
=cd
++;
}
else
x
=mp
[s
];
if(!mp
[t
])
{
mp
[t
]=cd
;
y
=cd
++;
}
else
y
=mp
[t
];
lu
[cl
++]=tnode(x
,y
,v
);
}
cin
>>s
>>t
;
if(s
==t
)
{
printf("0\n");
continue;
}
if(!mp
[s
]||!mp
[t
])
{
printf("-1\n");
continue;
}
ss
=mp
[s
];
ee
=mp
[t
];
cnt
=0;
for(int i
=1;i
<=n
;i
++)
head
[i
]=-1;
for(int i
=0;i
<cl
;i
++)
add(lu
[i
].x
,lu
[i
].y
,lu
[i
].v
);
dij(ss
);
if(dis
[ee
]==inf
)
{
printf("-1\n");
continue;
}
for(int i
=1;i
<=n
;i
++)
td
[i
]=dis
[i
];
cnt
=0;
for(int i
=1;i
<=n
;i
++)
head
[i
]=-1;
for(int i
=0;i
<cl
;i
++)
add(lu
[i
].y
,lu
[i
].x
,lu
[i
].v
);
dij(ee
);
ll ans
=inf
;
for(int i
=0;i
<cl
;i
++)
ans
=min(ans
,td
[lu
[i
].x
]+dis
[lu
[i
].y
]+lu
[i
].v
/2);
printf("%lld\n",ans
);
}
return 0;
}
