2014
04-09

# 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

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

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++;
}
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;
}


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~), [email protected]
* 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要回溯