Graph Theory, C++ (gcc)

Graph Theory

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define ui unsigned int
#define f(i,n) for(int i = 0; i < n; i++)
#define ff(i, l, r) for(int i = l; i < (int)r; i++)
#define rf(i, r, l) for(int i = r; i > (int)l; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define vvi vector<vi>
#define vvl vector<vl>
#define vvpii vector<vii>
#define vvpll vector<vll>
#define si set<int>
#define sl set<ll>
#define sii set<pii>
#define sll set<pll>
#define mii map<int, int>
#define mll map<ll, ll>
#define mipii map<int, pii>
#define mlpii map<int, pll>
#define mipll map<ll, pii>
#define mlpll map<ll, pll>
#define mivi map<int, vi>
#define mlvi map<ll, vi>
#define mlvl map<ll, vl>
#define mci map<char, int>
#define mcvi map<char, vi>
#define mcvl map<char, vl>
#define max_heap_i priority_queue<int>
#define max_heap_pii priority_queue<pii>
#define min_heap_i priority_queue<int, vector<int>, greater<int>>
#define min_heap_pii priority_queue<pii, vector<pii>, greater<pii>>
#define pb push_back
#define all a.begin(), a.end()
#define sz size()
#define inf INT_MAX
#define llinf LONG_LONG_MAX
#define int ll
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

/*void bfs(vvi graph, int s) {
    int n = graph.size();
    bool visited[n];
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int x = q.top();
        for(int i = 0; i < graph[x].size(); i++) {
            
        }
    }
}*/

void dijkstra(vvpii graph, int n, int dist[]) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    bool visited[n];
    f(i,n) visited[i] = false;
    q.push({0, 0});
    dist[0] = 0;
    while(!q.empty()) {
        pii element = q.top();
        int x = element.S;
        q.pop();
        if(dist[x] < element.F) continue;
        for(int i = 0; i < graph[x].size(); i++) {
            dist[graph[x][i].F] = min(dist[graph[x][i].F], dist[x] + graph[x][i].S);
            q.push({dist[graph[x][i].F], graph[x][i].F});
        }
    }
    f(i, n) {
        cout << dist[i] << " ";
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    vvpii graph(n);
    int dist[n];
    f(i,n) {
        dist[i] = INT_MAX;
    }
    f(i,m) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].pb({v, w});
    }
    dijkstra(graph, n, dist);
}

signed main() {
    fast;
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}


run \| edit \| history \| help	0