PAT-CCCC练习：L2-001.紧急救援

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

struct node
{
    int to,cost;
};

typedef pair<int,int>P;

vector<node>v[maxn];
priority_queue<P,vector<P>,greater<P> >q; 

int main()
{
    //输入 
    //a点，b点，路径长度cost
    v[a].push_back(node(b,cost));
    //如果双向：v[b].push_back(a,cost);
    //初始化全部dis为inf
    //dis[起始点]=0
    q.push(P(dis[起始点],起始点));
    //把dis放前面是因为pair的特点是先排first
    while(!q.empty())
    {
        int a=q.top().first,b=q.top().second;
        q.pop();
        if(dis[b]<a)
            continue;
        for(int i=0;i<v[b].size();i++)
        {
            node e=v[b][i];
            if(dis[e.to]>dis[b]+e.cost)
            {
                dis[e.to]=dis[b]+e.cost;
                q.push(P(dis[e.to],to));
            }
        }
    } 
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>

using namespace std;

typedef pair<int, int>P;

struct node
{
    int to, cost; //能通向哪里以及路径长度
    node(int x = 0, int y = 0): to(x), cost(y) {}
};

vector<node>v[505];
priority_queue< P, vector<P> , greater<P> >q;

int n, m, s, d;
int helpman[505], pre[505], dis[505], cnt[505], people[505];
//依次代表：每个城市的救援人员数、记录在最短路中此城市的前导城市、
//到起始点的距离、起始到这个点的最短路径数目、起点到这个点最短路径下的最短救援人数
void print(int i)//输出路径
{
    if (i == s) //当到达起点时
    {
        printf("%d", i);
        return;
    }
    else
    {
        print(pre[i]);
        printf(" %d", i);
    }
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &d);
    //城市数目，快速通道条数（一会儿要输入的路径数），起始点，终点
    for (int i = 0; i < n; i++) //每个城市救援人员数目
        scanf("%d", &helpman[i]);

    for (int i = 1; i <= m; i++)
    {
        int a, b, c; //某城，另一个城，两点间路径长度
        scanf("%d%d%d", &a, &b, &c);
        //增加城市a的可选路径
        v[a].push_back(node(b, c));
        //双向路径，也增加b的
        v[b].push_back(node(a, c));
    }

    //进行初始化
    fill(dis, dis + 506, 0x7ffffff);
    dis[s] = 0; //自己到自己的距离为0
    people[s] = helpman[s]; //到达起始点只有起始点城市的救援人员
    cnt[s] = 1; //自己到自己算一条路径
    q.push(make_pair(dis[s], s)); //将起始点放入优先队列进行扩散

    while (!q.empty())
    {
        int a = q.top().first, b = q.top().second;
        //b代表当前作为过渡点对其他点进行松弛的城市，a代表被优化过的dis[b]
        q.pop();

        if (dis[b] < a) //已经被更好地优化了，那个更好的P(dis[b],b)用作过渡点就好，这个点就没什么用了
            continue;

        for (int i = 0; i < v[b].size(); i++) //对城市b可以松弛的点进行逐个松弛
        {
            node e = v[b][i];

            if (dis[e.to] > dis[b] + e.cost)
            {
                dis[e.to] = dis[b] + e.cost;
                cnt[e.to] = cnt[b]; //目前b到e.to只有1条，则e.to的最短路径数等于b
                people[e.to] = people[b] + helpman[e.to]; //将这个城市的救援队员加进去
                pre[e.to] = b; //记录前导路径，用来之后输出
                q.push(make_pair(dis[e.to], e.to)); //将优化点加进队列用来做过渡点松弛其他城市
            }
            else if (dis[e.to] == dis[b] + e.cost) //这里根据题意改动，与最普通的最短路不同
            {
                cnt[e.to] += cnt[b]; //b到e.to每增加一条最短路径，总最短路就增加cnt[b]个
                if (people[e.to] < people[b] + helpman[e.to]) //追求最短路的前提下尽可能地增加队员数目
                {
                    people[e.to] = people[b] + helpman[e.to];
                    pre[e.to] = b; //人数变了，路径选择也就变了
                }
            }
        }
    }
    //输出
    printf("%d %d\n", cnt[d], people[d]);
    print(d);

    return 0;
}