ACMhust1019Adangeroustrip帮我看看为什么不过吧!我的思路是：做两次最短路,一次是从1开始做,一次是从n开始做,然后再枚举每条边,假设边为（a,b）,则看看1到a的距离和n到b的距离加上（a,b）的

Question

ACM hust 1019 A dangerous trip
帮我看看为什么不过吧!
我的思路是：做两次最短路,一次是从1开始做,一次是从n开始做,然后再枚举每条边,假设边为（a,b）,则看看1到a的距离和n到b的距离加上（a,b）的时间的一半,可是最后还是不过,看看这种思路有没有错,以下是代码
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=100001;
typedef pairpii;
priority_queueq;
struct node
{
int id,cost;
};
vectormap[N];
int d1[N],d2[N],n;
bool vis[N];
void dijkstra1(int k)
{
for (int i=1;i

Answer 1

我表示你的水平越来越高了,得跟你相互探讨,看下这个哈：
对每个点保存两个值,做两遍最短路：
第一次普通最长路,
第二遍做最短路时,对所有边枚举其缩到一半的情况,具体就是：
Dist[p->v][1] = min(Dist[i][0]+p->len/2.0, Dist[i][1]+p->len)