最短路

#include <cstdio>
#include <iotream>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

const int MAXN = 1005;
const int MAXM = 1000005;

int n;

struct edge
{
    int to;
    int cost;
    int next;
};

edge grap[MAXM];
int head[MAXN], tol;

void init()
{
    tol = 0;
    memset(head, -1, sizeof(head));
}

void add(int u, int v, int c)
{
    grap[tol].to = v;
    grap[tol].cost = c;
    grap[tol].next = head[u];
    head[u] = tol++;
}


struct node
{
    int key, value;
    bool operator < (const node & ohter) const
    {
        return value > other.value;
    }
};

int dis_dij[MAXN];
void dijkstra(int s)
{
    bool vis[MAX];
    for(int i = 1; i <= n; i++)
    {
        dis_dij[i] = INF;
        vis[i] = false;
    }

    dis_dij[s] = 0;
    vis[s] = true;

    priority_queue <node> q;
    q.push((node){s, dis_dij[s]});

    while(!q.empty())
    {
        int u = q.top();
        q.pop();

        if(vis[u]) continue;
        vis[u] = true;

        for(int i = head[u]; i != -1; i = grap[u].next)
        {
            int v = grap[i].to;
            int c = grap[i].cost;

            if(!vis[v] && dis[v] > dis[u] + c)
            {
                dis[v] = dis[u] + c;
                q.push((node){v, dis[v]});
            }
        }
    }
}

int dis_spfa[MAXN];
void spfa(int s)
{
    bool vis[MAXN];
    for(int i = 1; i <= n; i++)
    {
        dis_spfa[i] = INF;
        vis[i] = false;
    }

    dis_spfa[s] = 0;
    vis[s] = true;

    queue <int> q;
    q.push(s);

    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;

        for(int i = head[u]; i != -1; i = grap[i].next)
        {
            int v = grap[i].to;
            int c = grap[i].cost;
            if(dis[v] > dis[u] + c)
            {
                dis[v] = dis[u] + c;
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}