题目描述
N cities are connected by a network of M one-way roads. It is known that these roads do not cross outside the cities. The numeration of the cities and the roads starts from 1. One day, Haryy Potter must make a dangerous trip from city 1 to city N. Because there may have many monsters along the roads, he wants to finish this trip as soon as possible. Luckily, he knows a specil magic which can change the length of a road to half of the original length. But his magic is limited, and he can only use this magic once. Now give you the network, try to find the minumum time he can finish this dangerous trip.
输入
The first line contains an integer T,which means there are T test cases to be followed. For each test case: the first line contains two integer n and m, which are the number of vertices and edges int the network. Following the next m lines: each line describes an edge with three integers in the format: i, j, Cij.（cij is the time Haryy Potter must pay for from the city i to j if he don’t use magic） (0 < n <= 104, 0 < m < 105, 0 < i, j <= n, 0 < cij < 105)
输出
For each test case, output the minimum time he must pay for this dangerous trip.
样例输入
2 4 4 1 2 8 1 3 6 2 4 18 3 4 20 4 4 1 2 8 1 3 6 2 4 18 3 4 21
样例输出
16 16.5
一开始我是这样想的，d1[i]表示从起点到i的最短路，d2[i]表示从终点到i的最短路，然后枚举把每条边减半的情况，求最小值，但不知道为什么总是WA，于是在学长的点拨之下，改用dp，d1[i]表示不用魔法，d2[i]表示使用魔法，这样转移方程为d2[map[x][i].id]=min(d2[map[x][i].id],min(d1[x]+map[x][i].cost/2,d2[x]+map[x][i].cost));
当然这个转移方程是用vector写的，具体的还是看程序吧
#include<iostream> #include<cstdio> #include<vector> #include<utility> #include<queue> #include<cstring> using namespace std; const int N=100001; typedef pair<long long ,int>pii; priority_queue<pii,vector<pii>,greater<pii> >q; struct node { int id; long long cost; }; vector<node>map[N]; long long d1[N],d2[N]; long long tempmin1,Min,tempmin2; int n; bool vis[N]; void dijkstra1(int k) { for (int i=1;i<=n;i++) d1[i]=d2[i]=(i==k?0:999999999999); memset(vis,0,sizeof(vis)); q.push(make_pair(d1[k],k)); while(!q.empty()) { pii u=q.top();q.pop(); int x=u.second; if (!vis[x]) { vis[x]=true; for (int i=0;i<map[x].size();i++){ if(d1[map[x][i].id]>d1[x]+map[x][i].cost) { d1[map[x][i].id]=d1[x]+map[x][i].cost; q.push(make_pair(d1[map[x][i].id],map[x][i].id)); } d2[map[x][i].id]=min(d2[map[x][i].id],min(d1[x]+map[x][i].cost/2,d2[x]+map[x][i].cost));//这里就是转移方程 if (map[x][i].id==n) Min=min(d2[map[x][i].id],Min);//只有当==n的时候才更新 } } } } int main() { int t,m,x,y; long long z; int a[N],b[N]; long long c[N]; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for (int i=0;i<=n;i++) {map[i].clear();} for (int i=0;i<m;i++) { scanf("%d%d%lld",&x,&y,&z); node temp; a[i]=x;b[i]=y;c[i]=z*10; temp.id=y;temp.cost=z*10; map[x].push_back(temp); } Min=9999999999999; dijkstra1(1); if (Min%10==0)printf("%lld\n",Min/10); else printf("%lld.%lld\n",Min/10,Min%10); } return 0; }
hust 1019 A dangerous trip,布布扣,bubuko.com
原文：http://www.cnblogs.com/chensunrise/p/3721427.html