大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
这道题纠结了好久~~~最后发现最短路的算法求错了~~~
可是以前用此代码AC了好几道题了~~~汗~~求指点~
先是最后ac代码:
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define INF 1000010010
using namespace std;
int d[1005];
int vis[1005];
int w[1005][1005];
int s[1005];
void init(int n)
{
memset(s,0,sizeof(s));
memset(vis,0,sizeof(vis));
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
w[i][j]=INF;
if(i==j)
w[i][j]=0;
}
d[i]=INF;
}
}
int DFS(int k,int n)
{
if(s[k])
return s[k];
if(k == 2)
return 1;
for(int i=1; i<=n; i++)
{
if(w[k][i]!=INF && d[k]>d[i])
s[k]+=DFS(i,n);
}
return s[k];
}
struct cmp
{
bool operator()(int a,int b)
{
return a>b;
}
};
int main()
{
int n,m;
while(scanf("%d",&n),n!=0)
{
init(n);
scanf("%d",&m);
int i,a,b,d1;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&d1);
if(d1<w[a][b])
w[a][b]=w[b][a]=d1;
}
d[2]=0;
//priority_queue<int,vector<int>,cmp> q;
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
q.push(make_pair(d[2],2));
while(!q.empty())
{
pii t1=q.top();
q.pop();
int t=t1.second;
if(vis[t])
continue;
vis[t]=1;
for(i=1;i<=n;i++)
{
if(!vis[i]&&d[i]>d[t]+w[t][i])
{
d[i]=d[t]+w[t][i];
q.push(make_pair(d[i],i));
}
}
}
printf("%d\n",DFS(1,n));
}
return 0;
}
然后是WA的代码:
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define INF 1000010010
using namespace std;
int d[1005];
int vis[1005];
int w[1005][1005];
int s[1005];
void init(int n)
{
memset(s,0,sizeof(s));
memset(vis,0,sizeof(vis));
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
w[i][j]=INF;
if(i==j)
w[i][j]=0;
}
d[i]=INF;
}
}
int DFS(int k,int n)
{
if(s[k])
return s[k];
if(k == 2)
return 1;
for(int i=1; i<=n; i++)
{
if(w[k][i]!=INF && d[k]>d[i])
s[k]+=DFS(i,n);
}
return s[k];
}
struct cmp
{
bool operator()(int a,int b)
{
return d[a]>d[b]; //此处修改
}
};
int main()
{
int n,m;
while(scanf("%d",&n),n!=0)
{
init(n);
scanf("%d",&m);
int i,a,b,d1;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&d1);
if(d1<w[a][b])
w[a][b]=w[b][a]=d1;
}
d[2]=0;
priority_queue<int,vector<int>,cmp> q; //此处修改
//typedef pair<int,int> pii;
//priority_queue<pii,vector<pii>,greater<pii> > q;
q.push(2);
while(!q.empty())
{
int t=q.top();
q.pop();
//int t=t1.second;
if(vis[t])
continue;
vis[t]=1;
for(i=1;i<=n;i++)
{
if(!vis[i]&&d[i]>d[t]+w[t][i])
{
d[i]=d[t]+w[t][i];
q.push(i); //此次修改~~
}
}
}
printf("%d\n",DFS(1,n));
}
return 0;
}
感觉对的~~但是wa了 难道priority queue 用法有误么~~
~~知道问题了~~原来是priority_queue有问题~看看实现就知道了~q.push().q.pop() 都会排序
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/187309.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...