社区讨论

求助dalao,裸dijkstraWA了

P3371【模板】单源最短路径(弱化版)参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi6lqhz8
此快照首次捕获于
2025/11/20 06:56
4 个月前
此快照最后确认于
2025/11/20 06:56
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=1001,INF=0x3f3f3f3f;
int w[MAXN][MAXN];
bool v[MAXN];
int d[MAXN];
int n,m,s;
void dijkstra(int s){
    memset(v,false,sizeof(v));
    for(int i=1;i<=n;++i)
        d[i]=INF;
    d[s]=0;
    int x,m;
    for(int i=1;i<=n;++i){
        x=0,m=INF;
        for(int y=1;y<=n;++y)
            if(!v[y]&&d[y]<m){
                x=y;
                m=d[y];
            }
        if(!x)
            break;
        v[x]=true;
        for(int y=1;y<=n;++y)
            if(d[y]>d[x]+w[x][y])
                d[y]=d[x]+w[x][y];
    }
}
int main(){
    ios::sync_with_stdio(0);
    memset(w,0x3f,sizeof(w));
    cin>>n>>m>>s;
    int f,g;
    while(m--){
        cin>>f>>g;
        cin>>w[f][g];
    }
    dijkstra(s);
    for(int i=1;i<=n;++i){
        if(d[i]^INF)
            cout<<d[i]<<" ";
        else
            cout<<"2147483647 ";
    }
    return 0;
}
RT,怎么着也应该过70分啊

回复

6 条回复,欢迎继续交流。

正在加载回复...