【悬赏三关注】家人们这题恶心死了不想调了

Literally114514 @ 2023-10-03 23:53:03

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n,m,u,v,w,distant,ver,cnt=0,p;//cnt=编号 
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
struct node{
    int to;
    int w;
    int next;
};
int dist[100010];
bool used[100010];
node edge[100010];
int head[100010];
void add_edge(int u,int v,int w){
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
    cnt++;
}
int main(){
    cin>>n>>m>>p;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add_edge(u,v,w);
        //distant=first,end=second
    }
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    q.push({0,1});
    while(q.size()){
        auto k=q.top();
        q.pop(); 
        distant=k.first;
        ver=k.second;
        if(used[ver]) continue;
        used[ver]=1;
        for(int i=head[ver];i!=0;i=edge[i].next){
            int j=edge[i].to;
            if(edge[i].w+distant < dist[j]){
                dist[j]=edge[i].w+distant;
                q.push({dist[j],j});
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<dist[i]<<' ';
}

by DANNNqwq @ 2023-10-04 00:24:16

@Literally 关注就不用了qwq

by Literally114514 @ 2023-10-04 14:21:03

@DANNNsth 不行不行，必须给

by xuezhiyu @ 2023-10-11 22:17:43

在此奉上一些最短路算法的模板：

#include <queue>
#include <vector>
#include <iostream>

using namespace std;

const int inf = 2147483647;

struct edge {
    int v, w;

    edge(int _v, int _w) {
        v = _v, w = _w; 
    }
};

struct dijkstra_node {
    int dis, u;

    dijkstra_node(int _dis, int _u) {
        dis = _dis, u = _u;
    }

    bool operator>(const dijkstra_node& other) const {
        return dis > other.dis;
    }
};

struct graph {
    int n;
    vector<vector<edge>> _graph;

    graph() {}

    graph(int _n) {
        ready(_n);
    }

    void ready(int _n) {
        n = _n;
        _graph = vector<vector<edge>>(n + 1, vector<edge>());
    }

    void add_edge(int u, int v, int w) {
        _graph[u].push_back(edge(v, w));
    }

    // floyd-warshell算法求全源最短路，返回值表示dis数组
    vector<vector<int>> floyd_warshell() {
        vector<vector<int>> dis(n + 1, vector<int>(n + 1, inf));
        for (int i = 1; i <= n; i++) {
            dis[i][i] = 0;
            for (edge e : _graph[i]) {
                dis[i][e.v] = e.w;
            }
        }
        for (int t = 1; t <= n; t++) {
            for (int u = 1; u <= n; u++) {
                for (int v = 1; v <= n; v++) {
                    if (dis[u][t] == inf || dis[t][v] == inf) {
                        continue;
                    }
                    dis[u][v] = min(dis[u][v], dis[u][t] + dis[t][v]);
                }
            }
        }
        return dis;
    }

    // bellman-ford算法求单源最短路和是否存在从s点可以到达的负环，返回值pair的vector<int>表示dis数组，bool表示是否存在从s点可以到达的负环
    pair<vector<int>, bool> bellman_ford(int s) {
        vector<int> dis(n + 1, inf);
        dis[s] = 0;
        bool flag;
        for (int i = 1; i <= n; i++) {
            flag = false;
            for (int u = 1; u <= n; u++) {
                if (dis[u] == inf) {
                    continue;
                }
                for (edge e : _graph[u]) {
                    int v = e.v, w = e.w;
                    if (dis[v] > dis[u] + w) {
                        flag = true;
                        dis[v] = dis[u] + w;
                    }
                }
            }
            if (!flag) {
                break;
            }
        }
        return pair<vector<int>, bool>(dis, flag);
    }

    // spfa算法求单源最短路和是否存在从s点可以到达的负环，是bellman-ford的队列优化
    pair<vector<int>, bool> spfa(int s) {
        bool flag = false;
        queue<int> q;
        vector<bool> vis(n + 1, false);
        vector<int> dis(n + 1, inf), cnt(n + 1, 0);
        dis[s] = 0, vis[s] = true;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop(), vis[u] = false;
            for (edge e : _graph[u]) {
                int v = e.v, w = e.w;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) {
                        return pair<vector<int>, bool>(dis, true);
                    }
                    if (!vis[v]) {
                        q.push(v), vis[v] = 1;
                    }
                }
            }
        }
        return pair<vector<int>, bool>(dis, flag);
    }

    // dijkstra算法求单源最短路，不允许有负权边
    vector<int> dijkstra(int s) {
        vector<int> dis(n + 1, inf);
        vector<bool> vis(n + 1, false);
        priority_queue<dijkstra_node, vector<dijkstra_node>, greater<dijkstra_node>> q;
        dis[s] = 0;
        q.push(dijkstra_node(0, s));
        while (!q.empty()) {
            int u = q.top().u; q.pop();
            if (vis[u]) {
                continue;
            }
            vis[u] = true;
            for (edge e : _graph[u]) {
                int v = e.v, w = e.w;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    q.push(dijkstra_node(dis[v], v));
                }
            }
        }
        return dis;
    }
};