入门与面试求助
  • 板块题目总版
  • 楼主HYdroKomide
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/7/11 22:37
  • 上次更新2023/11/4 15:03:32
查看原帖
入门与面试求助
299883
HYdroKomide楼主2021/7/11 22:37

B3602,用了普通的Dijkstra,为什么会WA一个点?

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const long long inf=0x3f3f3f3f3f3f3f;
long long n,m,s=1,u,v,w,dis[300001];
bool vis[300001];
struct node{long long pos,dis;};
bool operator>(node x,node y){return x.dis>y.dis;}
vector<long long>g[300001],e[300001];
priority_queue<node,vector<node>,greater<node> >q;
void dijkstra(){
    memset(dis,inf,sizeof(dis));
	dis[s]=0;
    q.push(node{s,0});
    while(!q.empty()){
        long long u=q.top().pos;
        q.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(long long j=0;j<g[u].size();j++)
            if(dis[g[u][j]]>dis[u]+e[u][j]){
                dis[g[u][j]]=dis[u]+e[u][j];
                if(!vis[g[u][j]])q.push(node{g[u][j],dis[g[u][j]]});
            }
    }
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		g[u].push_back(v);
		e[u].push_back(w);
	}
	dijkstra();
	for(long long i=1;i<=n;i++){
	    if(dis[i]==inf)printf("-1 ");
	    else printf("%lld ",dis[i]);
	}
	printf("\n");
	return 0;
}
2021/7/11 22:37
加载中...