HDU 1535 POJ 1511 Invitation Cards

Description

1~n个城市m条单向路，求从1到各城市最短路之和与各城市到1最短路之和，两者的和

求第二者只需反向建边

题目链接

Code

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000005;
const int INF = 0x3f3f3f3f;

struct node
{
    int from, to, w, pre;
}a[N];

int head[N], dis[N], b[N], c[N], d[N], tot, sum, n, m, cnt;
bool vis[N];

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
        dis[i] = INF, head[i] = -1, vis[i] = 0;
    return ;
}

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
    cnt++;
}

void spfa(int start)
{
    deque<int> q;
    dis[start] = 0;
    q.push_front(start);
    vis[start] = 1;
    tot = 1;
    sum = 0;
    while(q.size())
    {
        int first = q.front();
        q.pop_front();
        vis[first] = 0;
        tot--;
        sum -= dis[first];
        for(int i = head[first]; ~i; i = a[i].pre)
        {
            int t = a[i].to;
            if(dis[t] > dis[first] + a[i].w)
            {
                dis[t] = dis[first] + a[i].w;
                if(!vis[t])
                {
                    vis[t] = 1;
                    if(q.empty() || dis[t] > dis[q.front()] || dis[t] * tot >= sum)
                        q.push_back(t);
                    else
                        q.push_front(t);
                    sum += dis[t];
                    tot++;
                }
            }
        }
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        long long ans = 0;
        init();
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &b[i], &c[i], &d[i]);
            add(b[i], c[i], d[i]);
        }
        spfa(1);
        for(int i = 1; i <= n; ++i)
            ans += dis[i];
        init();
        for(int i = 0; i < m; ++i)
            add(c[i], b[i], d[i]);
        spfa(1);
        for(int i = 1; i <= n; ++i)
            ans += dis[i];
        cout << ans << '\n';
    }
    return 0;
}