求助,Re了,玲姐举证

P4779 【模板】单源最短路径(标准版)

AndyCGM @ 2024-03-22 06:35:13

#include <iostream>
#include <cmath>
using namespace std;
int map[10100][10100];
int inf=0x3f3f3f3f;
int n,m,s;
int solve(int start){
    //Get ready.
    int result[10100],lastpoint[10100]={0},vis[10100]={0};
    for (int i=1; i<=n; i++)    result[i]=inf;
    result[start]=0;
    lastpoint[start]=start;
    //Start the main topic.
    for (int trytime=1; trytime<=n; trytime++){
        int sv=inf;//Smallest value
        int svi=0;//Snakkest value's index
        //Find the dot's ax vallue is smallest
        for (int index=1; index<=n; index++){
            if (result[index]<sv && vis[index]==0){
                sv=result[index];
                svi=index;
            }
        }
        int i=svi;
        for (int j=1; j<=n; j++){
            //If the dots i,j are connected dirrectly and i was unsettled.
            if (map[i][j]!=0 && vis[j]==0){
                //Caculate the Aproxed shortest way.
                int approx=result[i]+map[i][j];
                //If we find a better way, then we change the approx anwser.
                if (approx<result[j]){
                    result[j]=approx;
                    lastpoint[j]=i;    
                }
            }
        }
        //Settle this point
        vis[i]=1;
    }
    for (int i=1; i<=n; i++){
        if (result[i]==inf) cout << -1;
        else    cout << result[i];
        cout << " ";
    }
}

int main(){
    cin >> n >> m >> s;
    for (int i=1; i<=m; i++){
        int u,v,w;
        cin >> u >> v >> w;
        if (map[u][v]==0){
            map[u][v]=w;
        }else{
            if (w<map[u][v]){
                map[u][v]=w;
            }
        }
    }
    solve(s);
    return 0;
}

by Tomle @ 2024-03-22 06:54:57

数组开大了,别用邻接矩阵


by InversionShadow @ 2024-03-22 07:47:09

@AndyChen130130 n\le10^5,邻接矩阵不行


by _yukinoshita_yukino @ 2024-04-19 09:48:24

用堆优化


by Kevin1027 @ 2024-06-23 16:57:10

玲姐举证,不能开1(⊙﹏⊙)1e5


|