dijRE求调

P4779 【模板】单源最短路径（标准版）

ofthemoon @ 2024-12-11 22:12:45

#include <bits/stdc++.h>
using namespace std;
const int Inf=1e9;
const int maxn=2e5+5;
int n,m,s;
int f[5500][5500],dis[maxn]={Inf};
bool flag[maxn];
int main()
{
    cin>>n>>m>>s;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f[i][j]=Inf;
    for(int i=1; i<=m; i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        f[x][y]=w;
    }
    for(int i=1; i<=n; i++)
        dis[i]=f[s][i];
    dis[s]=0;
    flag[s]=true;
    for(int i=1; i<n; i++)
    {
        int k=0;
        for(int j=1; j<=n; j++)
            if(dis[k] > dis[j] && !flag[j])
                k=j;
        flag[k]=true;
        for(int j=1; j<=n; j++)
            if(!flag[j])
                dis[j]=min(dis[j],dis[k]+f[k][j]);
    }
    for(int i=1; i<=n; i++)
        cout<<dis[i]<<' ';
    return 0;
}

by ppyycc @ 2024-12-11 22:20:19

##### ~~我点开惊奇地看到我竟然做过这题~~ 这是我的代码： ```cpp #include<bits/stdc++.h> constexpr auto INF = 0x3f3f3f3f; using namespace std; const int MaxN = 100010, MaxM = 500010; int n, m, s, head[MaxN], dis[MaxN], cnt; bool vis[MaxN] = { false }; struct edge { int to, dis, next; }; edge e[MaxM]; void addedge(int u, int v, int d) { cnt++; e[cnt].dis = d; e[cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } struct node { int dis; int pos; bool operator <(const node x)const { return x.dis < dis; } }; priority_queue<node> q; void dijkstra() { memset(dis, INF, sizeof(dis)); dis[s] = 0; q.push(node{ 0, s }); while (!q.empty()) { node tmp = q.top(); q.pop(); int x = tmp.pos, d = tmp.dis; if (vis[x]) continue; vis[x] = 1; for (int i = head[x]; i; i = e[i].next) { int y = e[i].to; if (dis[y] > dis[x] + e[i].dis) { dis[y] = dis[x] + e[i].dis; if (!vis[y]) { q.push(node{ dis[y], y }); } } } } } int main() { cin >> n >> m >> s; for (int i = 0; i < m; i++) { int u, v, d; cin >> u >> v >> d; addedge(u, v, d); } dijkstra(); for (int i = 1; i <= n; i++)cout << dis[i] << ' '; return 0; } ```
|