首页 > ACM题库 > HDU-杭电 > HDU 3499-Flight-动态规划-[解题报告]HOJ
2014
04-09

HDU 3499-Flight-动态规划-[解题报告]HOJ

Flight

问题描述 :

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?

输入:

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.

输出:

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.

样例输入:

4 4
Harbin Beijing 500
Harbin Shanghai 1000
Beijing Chengdu 600
Shanghai Chengdu 400
Harbin Chengdu

4 0
Harbin Chengdu

样例输出:

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.

自认为相当正确的代码,交上去TLE了。以为是自己的方法错了,从昨晚开始想,到底错哪了?昨晚上看到了熟人的代码,依然大牛。网上的解法大多是正反向最短路+枚举折半边。这样得出。但是我的代码是:用dist[x][0]记录到x点使用折半票的花费,dist[x][1]记录到x点全票的花费。这样dp方程就很容易出来了… 自己想吧。

今天下午改了改,发现这题光读入数据就要3600ms++,最终发现是我的spfa速度慢了。再继续追下去,发现是我的spfa用的数据结构不对,我用的栈,人家ac的用的队列。我的发现总结一下吧:

1.spfa用队列比用栈快,特别是在边很多的情况。

2.用STL的队列和栈的速度比自己实现的栈速度快。

3.dist[10000][2]>dist1[10000]+dist2[10000]>dist[2][10000],读取速度依次减少。

终于还是让哥给切掉了! 哇卡卡卡!

#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<map>
#define MAXN 111111
#define MAXM 555555
const __int64 INF=(_I64_MAX)>>1;
//const __int64 INF=4611686018427387903;
using namespace std;

struct node
{
 	   int v;
	   __int64 price;
 	   node* next;
}Edge[MAXM],*ptr[MAXN];

int EdgeNum;
int N,M;//N node,M edge
 	
void addEdge( int u,int v,__int64 price )
{
 	 node *p=&Edge[EdgeNum++];
 	 p->price=price;
 	 p->v=v;
 	 p->next=ptr[u];
 	 ptr[u]=p;
}

__int64 dist[2][MAXN];
bool inS[MAXN];

__int64 spfa( int src,int dst )
{
 	 for( int i=0;i<=N;i++ )
 	 {
 	 	  dist[1][i]=dist[0][i]=INF;
 	 	  inS[i]=false;
	 }
 	 queue<int>myQ;
 	 dist[1][src]=dist[0][src]=0;
 	 
	 int top=0;
	 myQ.push(src);
 	 inS[src]=true;
 	 
 	 while( !myQ.empty() )
 	 {
	  		int cur=myQ.front();
	  		myQ.pop();
	  		node *p=ptr[cur];
	  		while( p )
	  		{
			 	   bool flag=false;
			 	   if( dist[1][p->v]>dist[1][cur]+p->price )
			 	   	   dist[1][p->v]=dist[1][cur]+p->price,flag=true;
			 	   	   
			 	   if( dist[0][p->v]>dist[0][cur]+p->price ||  dist[0][p->v]>dist[1][cur]+p->price/2 )
					   dist[0][p->v]=min( dist[0][cur]+p->price,dist[1][cur]+p->price/2 ),flag=true;
				   
				   if( flag && inS[p->v]==false )
	   	   		   {
	   	   		   	   myQ.push(p->v);
		   	   	   	   inS[p->v]=true;
  	   			   }
			 	   p=p->next;
 	   		}
	  		inS[cur]=false;
	 }
	 return dist[0][dst];
}

string str1,str2;

int main()
{
 	while( scanf( "%d %d",&N,&M )!=EOF )
 	{
	 	   memset( ptr,0,sizeof(ptr) );
	 	   EdgeNum=0;
		   map<string,int>map;
 	 	   int citynum=1;
		   __int64 price;
		   //cout<<INF<<endl;
   	   	   map.clear();
   	   	   
		   for( int i=1;i<=M;i++ )
		   {
		   		cin>>str1>>str2>>price;
		   		if( map.find(str1)==map.end() )
		   			map[str1]=citynum++;
		   		if( map.find(str2)==map.end() )
		   			map[str2]=citynum++;
		   		addEdge( map[str1],map[str2],price );
   		   }
	 	   cin>>str1>>str2;
	 	   //若SE城市中没有可去的边 
	 	   if( map.find(str1)==map.end() || map.find(str2)==map.end() )
	 	   {
	 	   	   printf("-1\n"); continue;
		   }
		   //S==E
		   else if( str1==str2 )
		   {
	 	   	    printf("0\n"); continue;
   		   }
   		   
	 	   __int64 ans=spfa( map[str1],map[str2] );
	 	   
		   if( ans==INF )
           	   printf("-1\n");
		   else
           	   printf("%I64d\n",ans);
  	}
  	return 0;
}

参考:http://blog.csdn.net/bysen32/article/details/7345252


  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), niwenxianq@qq.com
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  3. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯