hdu 3499 Flight (最短路径)
2024-10-19 17:32:40
Flight
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 2014 Accepted Submission(s): 428
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
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
Harbin Beijing 500
Harbin Shanghai 1000
Beijing Chengdu 600
Shanghai Chengdu 400
Harbin Chengdu
4 0
Harbin Chengdu
Sample Output
800
-1
-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
Recommend
题意：
在N个点，M条带权边的图上，查询从点s到点e的最短路径，不过，可以有一次机会可以把一条边的权值变成原来的一半。
小菜代码(双向求解，G++不能过...)：
//6890MS 41488K 2295 B C++
/*
建图双向求解
*/
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<string>
#define N 100005
using namespace std;
struct node{
__int64 v,w;
node(__int64 a,__int64 b){
v=a;w=b;
}
};
const __int64 inf=(_I64_MAX)/;
__int64 dis[][N];
bool vis[N];
__int64 from[*N],to[*N],weight[*N]; //记录边信息
vector<node>V[][N];
map<string,__int64>M;
__int64 n,m,sign;
__int64 start,end;
void spfa()
{
__int64 s;
if(sign==) s=start;
else s=end;
for(int i=;i<=n;i++)
dis[sign][i]=inf;
memset(vis,false,sizeof(vis));
queue<int>Q;
Q.push(s);
dis[sign][s]=;
while(!Q.empty()){
int u=Q.front();
Q.pop();
vis[u]=false;
int n0=V[sign][u].size();
for(int i=;i<n0;i++){
__int64 v=V[sign][u][i].v;
__int64 w=V[sign][u][i].w;
if(dis[sign][v]>dis[sign][u]+w){
dis[sign][v]=dis[sign][u]+w;
if(!vis[v]){
Q.push(v);
vis[v]=true;
}
}
}
}
}
int main(void)
{
string a,b;
__int64 c;
while(cin>>n>>m)
{
M.clear();
for(int i=;i<=n;i++){
V[][i].clear();
V[][i].clear();
}
int id=;
for(int i=;i<m;i++){
cin>>a>>b>>c;
if(M[a]==) M[a]=++id;
if(M[b]==) M[b]=++id;
V[][M[a]].push_back(node(M[b],c));
V[][M[b]].push_back(node(M[a],c));
from[i]=M[a];
to[i]=M[b];
weight[i]=c;
}
cin>>a>>b;
if(M[a]== || M[b]==){
puts("-1");continue;
}
start=M[a];
end=M[b]; if(start==end){
puts("");continue;
} sign=;
spfa();
if(dis[sign][end]==inf){
puts("-1");continue;
} sign=;
spfa(); __int64 ans=inf;
for(int i=;i<m;i++){
ans=min(ans,dis[][from[i]]+dis[][to[i]]+weight[i]/);
}
if(ans==inf) puts("-1");
else printf("%I64d\n",ans);
}
return ;
}
分层图思想：
//6078MS 23744K 1906 B C++
/* 转自：http://yomean.blog.163.com/blog/static/189420225201110282390985/ 一看就想到了分层图，不过如果用分层图，有点杀鸡用牛刀的感觉，因为只有两层。但我还是写了，最后AC了。不过网上很多人都是用建反两向边求解。
而对于分层图求最短路径问题，我们要注意的是，层与层之间的连线都是单向的，而且是从下一层指向上一层，而我们求最短路径的时候，起点总是在下一层，而终点总是在上一层，所以我们可以将经过层与层之间的特殊边的数目控制在n - 1(n是层数）。 */
#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<map>
#include<vector>
#define N 100005
#define inf (_I64_MAX)/2
using namespace std;
int n,m;
int head[*N],vis[*N];
int now,index,k;
__int64 dis[*N];
char name[N][];
map<string,int>M;
struct node{
int v,w,next;
}edge[*N];
void addedge(int u,int v,int w)
{
edge[index].v=v;
edge[index].w=w;
edge[index].next=head[u];
head[u]=index++;
}
struct cmp{
bool operator()(int a,int b){
return dis[a]>dis[b];
}
};
priority_queue<int,vector<int>,cmp>Q;
void init()
{
while(!Q.empty()) Q.pop();
M.erase(M.begin(),M.end());
for(int i=;i<*n;i++){
vis[i]=false;
head[i]=-;
}
now=;
index=;
}
void dij(int s,int e)
{
for(int i=;i<=*n;i++){
dis[i]=inf;vis[i]=false;
}
dis[s]=;
vis[s]=true;
Q.push(s);
while(!Q.empty()){
int u=Q.top();
Q.pop();
if(u==e){
printf("%I64d\n",dis[u]);
return;
}
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
int w=edge[i].w;
if(!vis[v] && dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
Q.push(v);
}
}
}
}
int main(void)
{
string a,b;
int x,y,c;
while(cin>>n>>m)
{
init();
for(int i=;i<m;i++){
cin>>a>>b>>c;
if(M.find(a)==M.end()) M[a]=now++;
if(M.find(b)==M.end()) M[b]=now++;
addedge(M[a],M[b],c);
addedge(M[a]+n,M[b]+n,c);
addedge(M[a]+n,M[b],c/);
}
cin>>a>>b;
__int64 ans=inf;
if(M.find(a)==M.end() || M.find(b)==M.end()){
puts("-1");continue;
}
else dij(M[a]+n,M[b]);
}
return ;
}
找了一个G++能过的，不过没自己实现，略感无语
//3765MS 28756K 2269 B G++
//转载： http://blog.csdn.net/shoutmon/article/details/8583984
/* 思路： 1.先正向建图，以a为源点跑Dijkstra 2.再反向建图，以b为源点跑Dijkstra 3.枚举边（作为花费变为一半的边），从a到这条边的起点u使用正向建图的结果，从这条边的终点v使用反向建图的结果，然后再加上这条边边权的一半，就得到这条边花费变为一半时候的总花费。 4.将枚举结果取最小值即为最小花费 5.注意输入是字符串，可以用map */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map> using namespace std; typedef __int64 ll; const int N=;
const int M=;
const ll inf=1LL<<; struct node
{
int to;
ll dis;
node *next;
}E[M<<],*G1[N],*G2[N],*head; int n,m,num;
ll d1[N],d2[N];
bool inq[N];
map<string,int> dict; inline void add(int a,int b,ll c,node *G[])
{
head->to=b;
head->dis=c;
head->next=G[a];
G[a]=head++;
} inline int change(char *s)
{
if(dict.count(s)) return dict[s];
else return dict[s]=num++;
} void SPFA(int s,ll d[],node *G[])
{ deque<int> Q;
Q.push_back(s);
memset(inq,false,sizeof(inq));
fill(d,d+N,inf);
d[s]=;
int to;
ll dis;
while(!Q.empty())
{
int u=Q.front();
Q.pop_front();
inq[u]=false;
for(node *p=G[u];p;p=p->next)
{
to=p->to;
dis=p->dis;
if(d[to]>d[u]+dis)
{
d[to]=d[u]+dis;
if(!Q.empty())
{
if(d[to]>d[Q.front()]) Q.push_back(to);
else Q.push_front(to);
}
else Q.push_back(to);
}
}
}
} int main()
{
char s1[],s2[];
while(~scanf("%d%d",&n,&m))
{
num=;
dict.clear();
memset(G1,NULL,sizeof(G1));
memset(G2,NULL,sizeof(G2));
head=E;
int s,t;
ll dis;
for(int i=;i<m;i++)
{
scanf("%s %s %I64d",s1,s2,&dis);
s=change(s1),t=change(s2);
add(s,t,dis,G1);
add(t,s,dis,G2);
}
scanf("%s %s",s1,s2);
s=dict[s1],t=dict[s2]; SPFA(s,d1,G1);
SPFA(t,d2,G2); ll ans=inf;
for(int i=;i<n;i++)
{
for(node *p=G1[i];p;p=p->next)
{
int j=p->to;
if(d1[i]<inf && d2[j]<inf) ans=min(ans,d1[i]+d2[j]+(p->dis)/);
}
} if(ans==inf) printf("-1\n");
else printf("%I64d\n",ans);
}
return ;
}
最新文章
- 【Unity Shaders】学习笔记
- c# 反射类字段
- Dom初
- javascript 深拷贝
- Linux基本命令之逻辑测试一
- Android 高级UI设计笔记01：使用ExpandableListView组件（ListView的扩展）
- bootstrap兼容IE8的一些注意
- 更新Android Studio 3.0碰到的问题
- pythonllk
- 压力测试工具ab - Apache HTTP server benchmarking tool
- AngularJS_简介、特性及基本使用_及其工作原理
- chrome扩展应用实例
- HBuilder ，及自用主题
- mac下安装cnpm淘宝镜像
- HTTP数据组织方式
- VM下设置CenOS为静态IP
- Linux命令之grep
- 【Maven】从Maven中导出项目依赖的Jar包
- Jmeter（三十五）聚合报告
- Android应用程序的结构