lplvvl @ 2024-11-15 23:53:39
自己可以看出来是dji判断是否被访问过的问题但是,不知道错那了,求大牛
#include<bits/stdc++.h>
using namespace std;
const int Mer=1e5+10;
int head[Mer],dis[Mer];
bool vis[Mer];
struct NOde{
int nexpointo,nexnumber,distancpo;
}a[2*Mer];
int k=0;
void ad(int u,int v,int w){
a[k].nexnumber=head[u];
a[k].nexpointo=v;
a[k].distancpo=w;
head[u]=k;
k++;
}
priority_queue< pair<int,int> , vector < pair<int,int> >,greater< pair <int,int> > >q;
void dji(int p){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(make_pair(0,p) );
vis[p]=true;
dis[p]=0;
while(!q.empty()){
int x=q.top().first,y=q.top().second;
q.pop();
vis[y]=true;
for(int i=head[y];i!=-1;i=a[i].nexnumber){
if(vis[a[i].nexpointo])continue;
if(dis[y]+a[i].distancpo<dis[a[i].nexpointo]){
q.push(make_pair(a[i].distancpo+dis[y],a[i].nexpointo));
dis[a[i].nexpointo]=dis[y]+a[i].distancpo;
}
}
}
}
int n,m,s,x,y,z;
int main(){
memset(head,-1,sizeof(head));
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
ad(x,y,z);
}
dji(1);
for(int i=1;i<=n;i++){
cout<<dis[i]<<" ";
}
}
就是这一段感觉出来有问题但是不会调
void dji(int p){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(make_pair(0,p) );
vis[p]=true;
dis[p]=0;
while(!q.empty()){
int x=q.top().first,y=q.top().second;
q.pop();
vis[y]=true;
for(int i=head[y];i!=-1;i=a[i].nexnumber){
if(vis[a[i].nexpointo])continue;
if(dis[y]+a[i].distancpo<dis[a[i].nexpointo]){
q.push(make_pair(a[i].distancpo+dis[y],a[i].nexpointo));
dis[a[i].nexpointo]=dis[y]+a[i].distancpo;
}
}
}
}
by 1nes @ 2024-11-16 10:46:52
void dji(int p){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(make_pair(0,p) );
// vis[p]=true;
dis[p]=0;
while(!q.empty()){
int x=q.top().first,y=q.top().second;
q.pop();
//判断
if(vis[y]) continue;
vis[y]=true;
for(int i=head[y];i!=-1;i=a[i].nexnumber){
if(vis[a[i].nexpointo])continue;
if(dis[y]+a[i].distancpo<dis[a[i].nexpointo]){
dis[a[i].nexpointo]=dis[y]+a[i].distancpo;
q.push(make_pair(a[i].distancpo+dis[y],a[i].nexpointo));
}
}
}
}
by 张心博harry @ 2024-12-16 18:19:43
%%%