【最短路】【DP】出行 trip

出行

trip.pas/c/cpp

1s/64MB

【题目描述】

某人打算外出旅游，他从起点城市1出发，计划到达城市n。城市之间被一些航线连通, 航线可以从任意方向飞行。由于是航空公司会员，他获得一次半价（半价以后价格只保留整数部分）机票的折扣券，使用的时机可以任意安排。

【输入】

输入第一行包含两个数n, m，表示城市数量和航线数量。

接下来的m行每行有3个数ai, bi, wi，分别表示第i条航线连接的第一个城市和第二个城市，以及航线的费用。

【输出】

输出一个整数，表示路途中花费的最小值。

【输出样例】

3 3

1 2 3

2 3 4

3 1 8

【输出样例】

4

【样例解释】

直接从 1号城市飞到3号城市并出示折扣券是最优方案

【数据规模】

对于30%的数据，n<=100,m<=100

对于50%的数据，n<=1000,m<=1500

对于所有数据，2<=n<=10000,1<=m<=100000, 1<=ai, bi<=n, wi<=10000,1<=n<=m。

保证存在一条路径可以从城市1到城市n的飞行方案

完成情况（cena测评）

本题实质上就是一个最短路，不过多了一个所谓的的优惠券

考试的时候写堆优的时候手残了一点！

一个简单的方法，我们可以再最短路的基础上加一维

用 d i st [ i ] [ 0 ] 表示走到 i 这个点还没用优惠券，用 d i s t [ i ] [ 1 ] 表示走到 i 这个店用了优惠券

那么我们就可以得到转移方程

f [ i ] [ 0 ] = m i n ( f [ i ] [ 0 ] , f [ j ] [ 0 ] + m a p [ i ] [ j ] )

f [ i ] [ 1 ] = m i n ( f [ i ] [ 1 ] , f [ j ] [ 0 ] + m a p [ i ] [ j ] / 2 )

f [ i ] [ 1 ] = m i n ( f [ i ] [ 1 ] , f [ j ] [ 1 ] + m a p [ i ] [ j ] )

这样就只需要在dijkstra里面套一个DP即可

不过考虑到数据范围是10000，所以写了一个堆优dijkstra

C++ AC Code

/*http://blog.csdn.net/jiangzh7
By Jiangzh*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<utility>
using namespace std;
const int N=10000+10;
const int V=100000+10;
const int inf=0x3f3f3f3f;int n,m;
struct link{int y,z;link *next;}*head[N];
int dist[N][2];
bool h[N];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > Q;void inlink(int x,int y,int z)
{link *node=new link;node->y=y;node->z=z;node->next=head[x];head[x]=node;
}void read()
{freopen("trip.in","r",stdin);freopen("trip.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);inlink(x,y,z);inlink(y,x,z);}
}void work()
{memset(dist,0x3f,sizeof(dist));dist[1][0]=dist[1][1]=0;Q.push(make_pair(0,1));while(!Q.empty()){pii u=Q.top();Q.pop();int k=u.second;if(h[k]) continue;h[k]=true;for(link *node=head[k];node;node=node->next)if(!h[node->y]){dist[node->y][0]=min(dist[node->y][0],dist[k][0]+node->z);dist[node->y][1]=min(dist[node->y][1],dist[k][1]+node->z);dist[node->y][1]=min(dist[node->y][1],dist[k][0]+node->z/2);Q.push(make_pair(min(dist[node->y][0],dist[node->y][1]),node->y));}}printf("%d\n",dist[n][1]);
}int main()
{read();work();return 0;
}