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;
}