HDU 1535（Invitation Cards）

使用 Dijkstra算法，首先构造正向图，计算从起点到达其余结点的最短距离；然后将正向图的所有边反向，构造反向图，再计算从起点到达其余结点的最短距离，此距离等于正向图中，从其余结点到达起点的最短距离。将两距离相加，即为从起点到达其余结点再返回起点的最短距离。

由于结点数很多，所以采用 vector 结构构造地图，在 Dijkstra 算法中采用优先队列。

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;

struct Node //结点
{
    int num, len; //结点编号，起点到达该结点的最短距离
    bool operator < (const Node& a) const {
        return len > a.len;
    }
};

int n, m; //结点数，边数
vector<Node> edge[MAXN]; //正向边集
vector<Node> redge[MAXN]; //反向边集
int dis[MAXN]; //起点到达其余各结点的最短距离
int vis[MAXN]; //结点访问情况

//Dijkstra算法，计算起点到达其余各结点的最短距离
void Dijkstra(vector<Node> G[])
{
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[1] = 0;

    priority_queue<Node> q;
    q.push(Node{ 1,0 }); //起点入队列
    while (!q.empty())
    {
        Node now = q.top();
        q.pop();
        int num = now.num;
        if (vis[num])
            continue;
        vis[num] = 1;
        for (int i = 0; i < G[num].size(); i++)
        {
            int next = G[num][i].num, len = G[num][i].len;
            if (!vis[next] && dis[next] > dis[num] + len)
            {
                dis[next] = dis[num] + len;
                q.push(Node{ next,dis[next] });
            }
        }
    }
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            edge[i].clear();
            redge[i].clear();
        }
        int a, b, c;
        while (m--)
        {
            cin >> a >> b >> c;
            edge[a].push_back(Node{ b,c }); //建立正向边
            redge[b].push_back(Node{ a,c }); //建立反向边
        }

        int ans = 0;
        Dijkstra(edge);
        for (int i = 1; i <= n; i++) //从起点到达其余结点
            ans += dis[i];
        Dijkstra(redge);
        for (int i = 1; i <= n; i++) //从其余结点返回起点
            ans += dis[i];
        cout << ans << endl;
    }
    return 0;
}

继续加油。