讨论 / 为什么dijsktra第五个点wrong answer
youyl 2013-10-28 04:45:00
点我顶贴 收藏 删除
本人使用dijsktra算法+二叉堆优化,同化缓冲区后可以得到80分,第五个点也没超时

但是第五个点答案错,求原因

测试点五:

测试结果错误.错误结果为:251224144346

escape

正确结果应为:160132265414

escape

另附代码:

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

long long dis[120001],c,d,t;

long long n,m,a,b,vis[120001],s;

priority_queue< pair<long long,long long> > q1;

vector<pair<long long,long long> >ad1[120001];

void dijs(int be)

{

for (int i=1;i<=n;i++)

{

dis[i]=-10;

vis[i]=0;

}dis[be]=0;

q1.push(make_pair(0,be));

while (!q1.empty())

{

c=-q1.top().first;

a=q1.top().second;

q1.pop();

for (int i=0;i<ad1[a].size();i++)

{

b=ad1[a][i].second;

d=c+ad1[a][i].first;

if(d<dis[b]||dis[b]<0){dis[b]=d;q1.push(make_pair(-d,b));}

}

}

}

int main()

{

ios::sync_with_stdio(0);

cin>>n>>m>>t;

for (int i=1;i<=m;i++)

{

cin>>a>>b>>c;

ad1[a].push_back(make_pair(c,b));

ad1[b].push_back(make_pair(c,a));

}

dijs(1);

for (int i=2;i<=n;i++)

{

s=s+dis[i]*2;

}

cout<<s<<endl;

if(s>t)cout<<"escape"<<endl;

else cout<<"run"<<endl;

return 0;

}

#1 xxyyttxx@2013-10-28 04:45:00
回复 删除
= =

第五个点错了

测试结果错误.错误结果为:251224144346

escape

正确结果应为:160132265414

escape

cheat 吧

查看更多回复
提交回复