C--最短路-二维数组会爆-Bellman-Ford 算法

    科技2022-07-17  108

    C–最短路 Description

    给出一个带权无向图,包含n个点,m条边。求出s,e的最短路。保证最短路存在。 Input

    多组输入。

    对于每组数据。

    第一行输入n,m(1<= n && n<=510^5,1 <= m && m <= 310^6)。 接下来m行,每行三个整数,u,v,w,表示u,v之间有一条权值为w(w >= 0)的边。 最后输入s,e。 Output

    对于每组数据输出一个整数代表答案。 Sample Input

    3 1

    1 2 3

    1 2

    Output

    3

    #include <bits/stdc++.h> using namespace std; int dis[500004], i, k, n, m, check, u[4000004], v[4000004], w[4000004]; void Bellman(); int main() { int s, e, x, y, z, t; while(scanf("%d %d", &n, &m) != EOF) { t = 1; for(i = 1; i <= m; i++) { scanf("%d %d %d", &x, &y, &z); u[t] = x, v[t] = y, w[t] = z; t++; u[t] = y, v[t] = x, w[t] = z; t++; } scanf("%d %d", &s, &e); m = m * 2; for(i = 1; i <= n; i++) dis[i] = INT_MAX; dis[s] = 0; Bellman(); printf("%d\n", dis[e]); } return 0; } void Bellman() //Bellman-Ford 算法 { for(k = 1; k < n; k++) { check = 0; for(i = 1; i <= m; i++) { if(dis[u[i]] != INT_MAX && dis[v[i]] > dis[u[i]] + w[i]) //如果不判断dis是否为最大值,可能会溢出 { dis[v[i]] = dis[u[i]] + w[i]; check = 1; } } if(check == 0) break; } return ; }

    //二维数组直接爆了

    #include<bits/stdc++.h> using namespace std; #define inf 999999 int a[50001][50001]; int visit[50001]; int dis[50001]; int n,m; int k; int minn; int s,e; int main() { while(cin>>n>>m) { memset(a,0,sizeof(a)); memset(visit,0,sizeof(visit)); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { if(i==j) a[i][j]=0; else a[i][j]=inf; } for(int i=0; i<m; i++) { int u,v,w; cin>>u>>v>>w; a[u][v]=a[v][u]=w; } cin>>s>>e; for(int i=1; i<=n; i++) { dis[i]=a[s][i]; } // for(int i=1; i<=n; i++) // cout<<dis[i]<<" "; visit[s]=1; for(int i=1; i<=n-1; i++) { minn=inf; for(int j=1; j<=n; j++) { if(visit[j]==0&&dis[j]<minn) { minn=dis[j]; k=j; } } visit[k]=1; for(int j=1; j<=n; j++) { if(a[k][j]<inf) { if(dis[j]>dis[k]+a[k][j]) dis[j]=dis[k]+a[k][j]; } } } // for(int i=1; i<=n; i++) // cout<<dis[i]<<" "; cout<<dis[e]<<endl; } return 0; } /*6 9 1 2 1 1 3 12 2 3 9 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4*/
    Processed: 0.010, SQL: 8