你可以试一下调试,我认为是你的变量有一点问题,位置也不大对。
by forever_0805 @ 2018-06-10 17:21:18
@[心之所爱](/space/show?uid=73809) 谢谢大佬回复!但要不是调试了很久也不会发帖了。。。
by 少帅_zjm @ 2018-06-10 17:24:38
您的cmp写错了吧
$qwq$
我也不知道,只是看起来是这样的
by Parabola @ 2018-06-10 17:38:08
每改变一次值似乎堆不会重新排序
by ybw051114 @ 2018-06-10 17:39:02
@[ybw051114](/space/show?uid=74346) 这应该不是问题所在,额虽然不会重新排序,但最小值还是应该能取
by 少帅_zjm @ 2018-06-10 18:03:11
```cpp
if(!vis[k] && d[u]+q[u][v].dis<d[k])
```
这个的逻辑有问题。不应该是在这里判断。Dijkstra应该是只取第一次出堆的值。但是可以多次进堆。可以参考一下题解的写法……
by panda_2134 @ 2018-06-10 18:21:56
```
#include <bits/stdc++.h>
using namespace std;
struct node
{
int v,dis;
}y;
int d[10005];
struct cmp
{
bool operator()(int a,int b)
{
return d[a]>d[b];
}
};
bool vis[10005]={false};
int n,m,s;
const int inf=1000000000;
priority_queue<int,vector<int>,cmp> qq;
vector<node> q[10005];
int main()
{
// int n,m;
// freopen("in.txt","r",stdin);
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
// cout<<a<<" "<<b<<" "<<c<<endl;
y.v=b;y.dis=c;
q[a].push_back(y);
}
fill(d,d+10005,inf);
d[s]=0;
qq.push(s);
while(!qq.empty())
{
// cout<<"fodji"<<endl;
int u=qq.top();
qq.pop();
// if(vis[u]) continue;
// cout<<u<<endl;
// vis[u]=1;
// cout<<u<<endl;
// cout<<q[u].size();
for(int v=0;v<q[u].size();v++)
{
// cout<<"gjfdo";
int k=q[u][v].v;
// printf("%d %d %d\n",d[u],q[u][v].dis,d[k]);
if(d[u]+q[u][v].dis<d[k])
{
d[k]=d[u]+q[u][v].dis;
qq.push(k);
}
}
}
for(int i=1;i<=n;i++)
{
if(d[i]==inf)
printf("2147483647 ");
else printf("%d ",d[i]);
}
}
```
这份略略改一下A了竟然
怎么这么神奇?当时我是看到了书上那几条句子觉得蛮有道理的加上去的
by 少帅_zjm @ 2018-06-10 18:54:17
@[panda_2134](/space/show?uid=23865) 谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢我终于明白了
by 少帅_zjm @ 2018-06-10 19:08:02