Code – 第193页

L2-001. 紧急救援-PAT团体程序设计天梯赛GPLT（Dijkstra算法）

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式：

输入第一行给出4个正整数N、M、S、D，其中N（2<=N<=500）是城市的个数，顺便假设城市的编号为0~(N-1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式：

第一行输出不同的最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出首尾不能有多余空格。

输入样例：
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2
输出样例：
2 60
0 1 3
分析：用一遍dijkstra算法。设立num[i]和w[i]表示从出发点到i结点拥有的路的条数，以及能够找到的救援队的数目～～当判定dis[u] + e[u][v] < dis[v]的时候，不仅仅要更新dis[v]，还要更新num[v] = num[u], w[v] = weight[v] + w[u]; 如果dis[u] + e[u][v] == dis[v]，还要更新num[v] += num[u]，而且判断一下是否权重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u];
再设立一个pre[i]表示最短路径的前一个结点，在dis[u] + e[u][v] <= dis[v]的时候更新pre[v] = u，最后递归打印路径即可

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, c1, c2;
int dis[510], weight[510], e[510][510], num[510], w[510], pre[510];
bool visit[510];
const int inf = 99999999;
void printPath(int v) {
    if(v == c1) {
        printf("%d", v);
        return ;
    }
    printPath(pre[v]);
    printf(" %d", v);
}
int main() {
    scanf("%d%d%d%d", &n, &m, &c1, &c2);
    for(int i = 0; i < n; i++)
        scanf("%d", &weight[i]);
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    int a, b, c;
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        e[a][b] = c;
        e[b][a] = c;
    }
    dis[c1] = 0;
    w[c1] = weight[c1];
    num[c1] = 1;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[u] + e[u][v] < dis[v]) {
                    dis[v] = dis[u] + e[u][v];
                    num[v] = num[u];
                    w[v] = w[u] + weight[v];
                    pre[v] = u;
                } else if(dis[u] + e[u][v] == dis[v]) {
                    num[v] = num[v] + num[u];
                    if(w[u] + weight[v] > w[v]) {
                        w[v] = w[u] + weight[v];
                        pre[v] = u;
                    }
                }
            }
        }
    }
    printf("%d %d\n", num[c2], w[c2]);
    printPath(c2);
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

int n, m, c1, c2;

int dis[510], weight[510], e[510][510], num[510], w[510], pre[510];

bool visit[510];

const int inf = 99999999;

void printPath(int v) {

if(v == c1) {

printf("%d", v);

return ;

}

printPath(pre[v]);

printf(" %d", v);

}

int main() {

scanf("%d%d%d%d", &n, &m, &c1, &c2);

for(int i = 0; i < n; i++)

scanf("%d", &weight[i]);

fill(e[0], e[0] + 510 * 510, inf);

fill(dis, dis + 510, inf);

int a, b, c;

for(int i = 0; i < m; i++) {

scanf("%d%d%d", &a, &b, &c);

e[a][b] = c;

e[b][a] = c;

}

dis[c1] = 0;

w[c1] = weight[c1];

num[c1] = 1;

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) break;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

num[v] = num[u];

w[v] = w[u] + weight[v];

pre[v] = u;

} else if(dis[u] + e[u][v] == dis[v]) {

num[v] = num[v] + num[u];

if(w[u] + weight[v] > w[v]) {

w[v] = w[u] + weight[v];

pre[v] = u;

}

printf("%d %d\n", num[c2], w[c2]);

printPath(c2);

return 0;

}

1003. Emergency (25)-PAT甲级真题（Dijkstra算法）

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Input

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (<= 500) – the number of cities (and the cities are numbered from 0 to N-1), M – the number of roads, C1 and C2 – the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.

Output

For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather.
All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

Sample Input

5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

Sample Output

2 4

题目大意：n个城市m条路，每个城市有救援小组，所有的边的边权已知。给定起点和终点，求从起点到终点的最短路径条数以及最短路径上的救援小组数目之和。如果有多条就输出点权（城市救援小组数目）最大的那个～

分析：用一遍Dijkstra算法～救援小组个数相当于点权，用Dijkstra求边权最小的最短路径的条数，以及这些最短路径中点权最大的值～dis[i]表示从出发点到i结点最短路径的路径长度，num[i]表示从出发点到i结点最短路径的条数，w[i]表示从出发点到i点救援队的数目之和～当判定dis[u] + e[u][v] < dis[v]的时候，不仅仅要更新dis[v]，还要更新num[v] = num[u], w[v] = weight[v] + w[u]; 如果dis[u] + e[u][v] == dis[v]，还要更新num[v] += num[u]，而且判断一下是否权重w[v]更小，如果更小了就更新w[v] = weight[v] + w[u];

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, c1, c2;
int e[510][510], weight[510], dis[510], num[510], w[510];
bool visit[510];
const int inf = 99999999;
int main() {
    scanf("%d%d%d%d", &n, &m, &c1, &c2);
    for(int i = 0; i < n; i++)
        scanf("%d", &weight[i]);
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    int a, b, c;
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        e[a][b] = e[b][a] = c;
    }
    dis[c1] = 0;
    w[c1] = weight[c1];
    num[c1] = 1;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[u] + e[u][v] < dis[v]) {
                    dis[v] = dis[u] + e[u][v];
                    num[v] = num[u];
                    w[v] = w[u] + weight[v];
                } else if(dis[u] + e[u][v] == dis[v]) {
                    num[v] = num[v] + num[u];
                    if(w[u] + weight[v] > w[v])
                        w[v] = w[u] + weight[v];
                }
            }
        }
    }
    printf("%d %d", num[c2], w[c2]);
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int n, m, c1, c2;

int e[510][510], weight[510], dis[510], num[510], w[510];

bool visit[510];

const int inf = 99999999;

int main() {

scanf("%d%d%d%d", &n, &m, &c1, &c2);

for(int i = 0; i < n; i++)

scanf("%d", &weight[i]);

fill(e[0], e[0] + 510 * 510, inf);

fill(dis, dis + 510, inf);

int a, b, c;

for(int i = 0; i < m; i++) {

scanf("%d%d%d", &a, &b, &c);

e[a][b] = e[b][a] = c;

}

dis[c1] = 0;

w[c1] = weight[c1];

num[c1] = 1;

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) break;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

num[v] = num[u];

w[v] = w[u] + weight[v];

} else if(dis[u] + e[u][v] == dis[v]) {

num[v] = num[v] + num[u];

if(w[u] + weight[v] > w[v])

w[v] = w[u] + weight[v];

}

printf("%d %d", num[c2], w[c2]);

return 0;

}

【最短路径】之Dijkstra算法

最短路径

单源最短路径：计算源点到其他各顶点的最短路径的长度
全局最短路径：图中任意两点的最短路径
Dijkstra、Bellman-Ford、SPFA求单源最短路径
Floyed可以求全局最短路径，但是效率比较低
SPFA算法是Bellman-Ford算法的队列优化
Dijkstra算法不能求带负权边的最短路径，而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
Bellman-Ford算法的核心代码只有4行，Floyd-Warshall算法的核心代码只有5行。
深度优先遍历可以求一个点到另一个点的最短路径的长度

Dijkstra算法

Dijkstra() {
  初始化;
  for(循环n次) {
    u = 使dis[u]最小的还未被访问的顶点的编号;
    记u为确定值;
    for(从u出发能到达的所有顶点v){
      if(v未被访问 && 以u为中介点使s到顶点v的最短距离更优)
        优化dis[v];
    }
  }
}

Dijkstra() {

初始化;

for(循环n次) {

u = 使dis[u]最小的还未被访问的顶点的编号;

记u为确定值;

for(从u出发能到达的所有顶点v){

if(v未被访问 && 以u为中介点使s到顶点v的最短距离更优)

优化dis[v];

}

//邻接矩阵
int n, e[maxv][maxv];
int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点
bool vis[maxv] = {false};
void Dijkstra(int s) {
  fill(dis, dis + maxv, inf);
  dis[s] = 0;
  for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身
  for(int i = 0; i < n; i++) {
    int u = -1, minn = inf;
    for(int j = 0; j < n; j++) {
      if(visit[j] == false && dis[j] < minn) {
        u = j;
        minn = dis[j];
      }
    }
    if(u == -1) return;
    visit[u] = true;
    for(int v = 0; v < n; v++) {
      if(visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] < dis[v]) {
        dis[v] = dis[u] + e[u][v];
        pre[v] = u; // pre用来标注当前结点的前一个结点
      }
    }
  }
}

//邻接矩阵

int n, e[maxv][maxv];

int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点

bool vis[maxv] = {false};

void Dijkstra(int s) {

fill(dis, dis + maxv, inf);

dis[s] = 0;

for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) return;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

pre[v] = u; // pre用来标注当前结点的前一个结点

}

//邻接表
struct node {
  int v, dis;
}
vector<node> e[maxv];
int n;
int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点
bool visit[maxv] = {false};
for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身
void Dijkstra(int s) {
  fill(dis, dis + maxv, inf);
  dis[s] = 0;
  for(int i = 0; i < n; i++) {
    int u = -1, minn = inf;
    for(int j = 0; j < n; j++) {
      if(visit[j] == false && dis[j] < minn) {
        u = j;
        minn = dis[j];
      }
    }
    if(u == -1) return ;
    visit[u] = true;
    for(int j = 0; j < e[u].size(); j++) {
      int v = e[u][j].v;
      if(visit[v] == false && dis[u] + e[u][j].dis < dis[v]) {
        dis[v] = dis[u] + e[u][j].dis;
        pre[v] = u;
      }
    }
  }
}

//邻接表

struct node {

int v, dis;

}

vector<node> e[maxv];

int n;

int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点

bool visit[maxv] = {false};

for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身

void Dijkstra(int s) {

fill(dis, dis + maxv, inf);

dis[s] = 0;

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) return ;

visit[u] = true;

for(int j = 0; j < e[u].size(); j++) {

int v = e[u][j].v;

if(visit[v] == false && dis[u] + e[u][j].dis < dis[v]) {

dis[v] = dis[u] + e[u][j].dis;

pre[v] = u;

}

void dfs(int s, int v) {
  if(v == s) {
    printf("%d\n", s);
    return ;
  }
  dfs(s, pre[v]);
  printf("%d\n", v);
}

void dfs(int s, int v) {

if(v == s) {

printf("%d\n", s);

return ;

}

dfs(s, pre[v]);

printf("%d\n", v);

}

三种附加考法：第一标尺是距离，如果距离相等的时候，新增第二标尺

新增边权（第二标尺），要求在最短路径有多条时要求路径上的花费之和最小

for(int v = 0; v < n; v++) { //重写v的for循环
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      c[v] = c[u] + cost[u][v];
    }else if(dis[u] + e[u][v] == dis[v] && c[u] + cost[u][v] < c[v]) {
      c[v] = c[u] + cost[u][v];
    }
  }
}

for(int v = 0; v < n; v++) { //重写v的for循环

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

c[v] = c[u] + cost[u][v];

}else if(dis[u] + e[u][v] == dis[v] && c[u] + cost[u][v] < c[v]) {

c[v] = c[u] + cost[u][v];

}

给定每个点的点权（第二标尺），要求在最短路径上有多条时要求路径上的点权之和最大

for(int v = 0; v < n; v++) {
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      w[v] = w[u] + weight[v];
    }else if(dis[u] + e[u][v] == dis[v] && w[u] + weight[v] > w[v]) {
      w[v] = w[u] + weight[v];
    }
  }
}

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

w[v] = w[u] + weight[v];

}else if(dis[u] + e[u][v] == dis[v] && w[u] + weight[v] > w[v]) {

w[v] = w[u] + weight[v];

}

直接问有多少条最短路径

增加一个数组num[]，num[s] = 1，其余num[u] = 0，表示从起点s到达顶点u的最短路径的条数为num[u]

for(int v = 0; v < n; v++) {
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      num[u] = num[v];
    }else if(dis[u] + e[u][v] == dis[v]) {
      num[v] = num[v] + num[u];
    }
  }
}

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

num[u] = num[v];

}else if(dis[u] + e[u][v] == dis[v]) {

num[v] = num[v] + num[u];

}

例子：比如说又要路径最短，又要点权权值最大，而且还要输出个数，而且还要输出路径

for(int v = 0; v < n; v++) {
  if(visit[v] == false && e[u][v] != inf) {
    if(dis[u] + e[u][v] < dis[v]) {
      dis[v] = dis[u] + e[u][v];
      num[v] = num[u];
      w[v] = w[u] + weight[v];
      pre[v] = u;
    } else if(dis[u] + e[u][v] == dis[v]) {
      num[v] = num[v] + num[u];
      if(w[u] + weight[v] > w[v]) {
        w[v] = w[u] + weight[v];
        pre[v] = u;
      }
    }
  }
}

void printPath(int v) {
    if(v == s) {
        printf("%d", v);
        return ;
    }
    printPath(pre[v]);
    printf("%d ", v);
}

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

num[v] = num[u];

w[v] = w[u] + weight[v];

pre[v] = u;

} else if(dis[u] + e[u][v] == dis[v]) {

num[v] = num[v] + num[u];

if(w[u] + weight[v] > w[v]) {

w[v] = w[u] + weight[v];

pre[v] = u;

}

void printPath(int v) {

if(v == s) {

printf("%d", v);

return ;

}

printPath(pre[v]);

printf("%d ", v);

}

of course, 可以不用这么麻烦，用Dijkstra求最短路径和pre数组，然后用深度优先遍历来获取想知道的一切，包括点权最大，边权最大，路径个数，路径
因为可能有多条路径，所以Dijkstra部分的pre数组使用vector<int> pre[maxv];

//Dijkstra部分
if(dis[u] + e[u][v] < dis[v]) {
  dis[v] = dis[u] + e[u][v];
  pre[v].clear();
  pre[v].push_back(u);
} else if(dis[i] + e[u] == dis[v]) {
  pre[v].push_back(u);
}

//Dijkstra部分

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

pre[v].clear();

pre[v].push_back(u);

} else if(dis[i] + e[u] == dis[v]) {

pre[v].push_back(u);

}

既然已经求得pre数组，就知道了所有的最短路径，然后要做的就是用dfs遍历所有最短路径，找出一条使第二标尺最优的路径

int optvalue;
vector<int> pre[maxv];
vector<int> path, temppath;
void dfs(int v) { // v为当前访问结点
  if(v == start) {
    temppath.push_back(v);
    int value = 路径temppath上的value值;
    if(value 优于 optvalue) {
      optvalue = value;
      path = temppath;
    }
    temppath.pop_back();
    return ;
  }
  temppath.push_back(v);
  for(int i = 0; i < pre[v].size(); i++)
    dfs(pre[v][i]);
  temppath.pop_back();
}

int optvalue;

vector<int> pre[maxv];

vector<int> path, temppath;

void dfs(int v) { // v为当前访问结点

if(v == start) {

temppath.push_back(v);

int value = 路径temppath上的value值;

if(value 优于 optvalue) {

optvalue = value;

path = temppath;

}

temppath.pop_back();

return ;

}

temppath.push_back(v);

for(int i = 0; i < pre[v].size(); i++)

dfs(pre[v][i]);

temppath.pop_back();

}

解释：
- 对于递归边界而言，如果当前访问的结点是叶子结点（就是路径的开始结点），那么说明到达了递归边界，把v压入temppath，temppath里面就保存了一条完整的路径。如果计算得到的当前的value大于最大值，就path = temppath，然后把temppath的最后一个结点弹出，return ;
- 对于递归式而言，每一次都是把当前访问的结点压入，然后找他的pre[v][i]，进行递归，递归完毕后弹出最后一个结点
计算当前temppath边权或者点权之和的代码：

// 边权之和
int value = 0;
for(int i = tempptah.size() - 1; i > 0; i--) {
  int id = temppath[i], idnext = temppath[i - 1];
  value += v[id][idnext];
}
// 点权之和
int value = 0;
for(int i = temppath.size(); i >= 0; i--) {
  int id = temppath[i];
  value += w[id];
}

// 边权之和

int value = 0;

for(int i = tempptah.size() - 1; i > 0; i--) {

int id = temppath[i], idnext = temppath[i - 1];

value += v[id][idnext];

}

// 点权之和

int value = 0;

for(int i = temppath.size(); i >= 0; i--) {

int id = temppath[i];

value += w[id];

}

计算路径直接在Dijkstra部分写就可以
例子：计算最短距离的路径和最小花费

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, s, d;
int e[510][510], dis[510], cost[510][510];
vector<int> pre[510];
bool visit[510];
const int inf = 99999999;
vector<int> path, temppath;
int mincost = inf;
void dfs(int v) {
    if(v == s) {
        temppath.push_back(v);
        int tempcost = 0;
        for(int i = temppath.size() - 1; i > 0; i--) {
            int id = temppath[i], nextid = temppath[i-1];
            tempcost += cost[id][nextid];
        }
        if(tempcost < mincost) {
            mincost = tempcost;
            path = temppath;
        }
        temppath.pop_back();
        return ;
    }
    temppath.push_back(v);
    for(int i = 0; i < pre[v].size(); i++)
        dfs(pre[v][i]);
    temppath.pop_back();
}
int main() {
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    scanf("%d%d%d%d", &n, &m, &s, &d);
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        scanf("%d", &e[a][b]);
        e[b][a] = e[a][b];
        scanf("%d", &cost[a][b]);
        cost[b][a] = cost[a][b];
    }
    pre[s].push_back(s);
    dis[s] = 0;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = j;
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[v] > dis[u] + e[u][v]) {
                    dis[v] = dis[u] + e[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                } else if(dis[v] == dis[u] + e[u][v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
    dfs(d);
    for(int i = path.size() - 1; i >= 0; i--)
        printf("%d ", path[i]);
    printf("%d %d", dis[d], mincost);
    return 0;
}
//注意路径path因为是从末端一直压入push_back到path里面的，所以要输出路径的时候倒着输出

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

int n, m, s, d;

int e[510][510], dis[510], cost[510][510];

vector<int> pre[510];

bool visit[510];

const int inf = 99999999;

vector<int> path, temppath;

int mincost = inf;

void dfs(int v) {

if(v == s) {

temppath.push_back(v);

int tempcost = 0;

for(int i = temppath.size() - 1; i > 0; i--) {

int id = temppath[i], nextid = temppath[i-1];

tempcost += cost[id][nextid];

}

if(tempcost < mincost) {

mincost = tempcost;

path = temppath;

}

temppath.pop_back();

return ;

}

temppath.push_back(v);

for(int i = 0; i < pre[v].size(); i++)

dfs(pre[v][i]);

temppath.pop_back();

}

int main() {

fill(e[0], e[0] + 510 * 510, inf);

fill(dis, dis + 510, inf);

scanf("%d%d%d%d", &n, &m, &s, &d);

for(int i = 0; i < m; i++) {

int a, b;

scanf("%d%d", &a, &b);

scanf("%d", &e[a][b]);

e[b][a] = e[a][b];

scanf("%d", &cost[a][b]);

cost[b][a] = cost[a][b];

}

pre[s].push_back(s);

dis[s] = 0;

for(int i = 0; i < n; i++) {

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = j;

}

if(u == -1) break;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[v] > dis[u] + e[u][v]) {

dis[v] = dis[u] + e[u][v];

pre[v].clear();

pre[v].push_back(u);

} else if(dis[v] == dis[u] + e[u][v]) {

pre[v].push_back(u);

}

dfs(d);

for(int i = path.size() - 1; i >= 0; i--)

printf("%d ", path[i]);

printf("%d %d", dis[d], mincost);

return 0;

}

//注意路径path因为是从末端一直压入push_back到path里面的，所以要输出路径的时候倒着输出

【C++】fill函数，fill与memset函数的区别

memset函数
- 按照字节填充某字符
- 在头文件<cstring>里面
fill函数
- 按照单元赋值，将一个区间的元素都赋同一个值
- 在头文件<algorithm>里面
因为memset函数按照字节填充，所以一般memset只能用来填充char型数组，（因为只有char型占一个字节）如果填充int型数组，除了0和-1，其他的不能。因为只有00000000 = 0，-1同理，如果我们把每一位都填充“1”，会导致变成填充入“11111111”

而fill函数可以赋值任何，而且使用方法特别简便：

fill(arr, arr + n, 要填入的内容);
例如：

#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int arr[10];
    fill(arr, arr + 10, 2);
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

int main() {

int arr[10];

fill(arr, arr + 10, 2);

return 0;

}

vector也可以：

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main(){
    vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    fill(v.begin(), v.end(), -1);
 	return 0;
}

#include <algorithm>

#include <vector>

#include <iostream>

using namespace std;

int main(){

vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

fill(v.begin(), v.end(), -1);

return 0;

}

而memset的使用方法是：

#include <iostream>
#include <cstring>
using namespace std;
int main(){
    int a[20];
    memset(a, 0, sizeof a);
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main(){

int a[20];

memset(a, 0, sizeof a);

return 0;

}

1016. Phone Bills (25)-PAT甲级真题

A long-distance telephone company charges its customers by the following rules:

Making a long-distance call costs a certain amount per minute, depending on the time of day when the call is made. When a customer starts connecting a long-distance call, the time will be recorded, and so will be the time when the customer hangs up the phone. Every calendar month, a bill is sent to the customer for each minute called (at a rate determined by the time of day). Your job is to prepare the bills for each month, given a set of phone call records.

Input Specification:

Each input file contains one test case. Each case has two parts: the rate structure, and the phone call records.

The rate structure consists of a line with 24 non-negative integers denoting the toll (cents/minute) from 00:00 – 01:00, the toll from 01:00 – 02:00, and so on for each hour in the day.

The next line contains a positive number N (<= 1000), followed by N lines of records. Each phone call record consists of the name of the customer (string of up to 20 characters without space), the time and date (mm:dd:hh:mm), and the word “on-line” or “off-line”.

For each test case, all dates will be within a single month. Each “on-line” record is paired with the chronologically next record for the same customer provided it is an “off-line” record. Any “on-line” records that are not paired with an “off-line” record are ignored, as are “off-line” records not paired with an “on-line” record. It is guaranteed that at least one call is well paired in the input. You may assume that no two records for the same customer have the same time. Times are recorded using a 24-hour clock.

Output Specification:

For each test case, you must print a phone bill for each customer.

Bills must be printed in alphabetical order of customers’ names. For each customer, first print in a line the name of the customer and the month of the bill in the format shown by the sample. Then for each time period of a call, print in one line the beginning and ending time and date (dd:hh:mm), the lasting time (in minute) and the charge of the call. The calls must be listed in chronological order. Finally, print the total charge for the month in the format shown by the sample.

Sample Input:
10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
10
CYLL 01:01:06:01 on-line
CYLL 01:28:16:05 off-line
CYJJ 01:01:07:00 off-line
CYLL 01:01:08:03 off-line
CYJJ 01:01:05:59 on-line
aaa 01:01:01:03 on-line
aaa 01:02:00:01 on-line
CYLL 01:28:15:41 on-line
aaa 01:05:02:24 on-line
aaa 01:04:23:59 off-line
Sample Output:
CYJJ 01
01:05:59 01:07:00 61 $12.10
Total amount: $12.10
CYLL 01
01:06:01 01:08:03 122 $24.40
28:15:41 28:16:05 24 $3.85
Total amount: $28.25
aaa 01
02:00:01 04:23:59 4318 $638.80
Total amount: $638.80

分析：将给出的数据先按照姓名排序，再按照时间的先后顺序排列，这样遍历的时候，前后两个名字相同且前面的状态为on-line后面一个的状态为off-line的就是合格数据～

注意：【关于最后一个测试点】计算费用从00:00:00到dd:hh:mm计算可以避免跨天的问题，比如01:12:00到02:02:00

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    string name;
    int status, month, time, day, hour, minute;
};
bool cmp(node a, node b) {
    return a.name != b.name ? a.name < b.name : a.time < b.time;
}
double billFromZero(node call, int *rate) {
    double total = rate[call.hour] * call.minute + rate[24] * 60 * call.day;
    for (int i = 0; i < call.hour; i++)
        total += rate[i] * 60;
    return total / 100.0;
}
int main() {
    int rate[25] = {0}, n;
    for (int i = 0; i < 24; i++) {
        scanf("%d", &rate[i]);
        rate[24] += rate[i];
    }
    scanf("%d", &n);
    vector<node> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i].name;
        scanf("%d:%d:%d:%d", &data[i].month, &data[i].day, &data[i].hour, &data[i].minute);
        string temp;
        cin >> temp;
        data[i].status = (temp == "on-line") ? 1 : 0;
        data[i].time = data[i].day * 24 * 60 + data[i].hour * 60 + data[i].minute;
    }
    sort(data.begin(), data.end(), cmp);
    map<string, vector<node> > custom;
    for (int i = 1; i < n; i++) {
        if (data[i].name == data[i - 1].name && data[i - 1].status == 1 && data[i].status == 0) {
            custom[data[i - 1].name].push_back(data[i - 1]);
            custom[data[i].name].push_back(data[i]);
        }
    }
    for (auto it : custom) {
        vector<node> temp = it.second;
        cout << it.first;
        printf(" %02d\n", temp[0].month);
        double total = 0.0;
        for (int i = 1; i < temp.size(); i += 2) {
            double t = billFromZero(temp[i], rate) - billFromZero(temp[i - 1], rate);
            printf("%02d:%02d:%02d %02d:%02d:%02d %d $%.2f\n", temp[i - 1].day, temp[i - 1].hour, temp[i - 1].minute, temp[i].day, temp[i].hour, temp[i].minute, temp[i].time - temp[i - 1].time, t);
            total += t;
        }
        printf("Total amount: $%.2f\n", total);
    }
    return 0;
}

#include <iostream>

#include <map>

#include <vector>

#include <algorithm>

using namespace std;

struct node {

string name;

int status, month, time, day, hour, minute;

};

bool cmp(node a, node b) {

return a.name != b.name ? a.name < b.name : a.time < b.time;

}

double billFromZero(node call, int *rate) {

double total = rate[call.hour] * call.minute + rate[24] * 60 * call.day;

for (int i = 0; i < call.hour; i++)

total += rate[i] * 60;

return total / 100.0;

}

int main() {

int rate[25] = {0}, n;

for (int i = 0; i < 24; i++) {

scanf("%d", &rate[i]);

rate[24] += rate[i];

}

scanf("%d", &n);

vector<node> data(n);

for (int i = 0; i < n; i++) {

cin >> data[i].name;

scanf("%d:%d:%d:%d", &data[i].month, &data[i].day, &data[i].hour, &data[i].minute);

string temp;

cin >> temp;

data[i].status = (temp == "on-line") ? 1 : 0;

data[i].time = data[i].day * 24 * 60 + data[i].hour * 60 + data[i].minute;

}

sort(data.begin(), data.end(), cmp);

map<string, vector<node> > custom;

for (int i = 1; i < n; i++) {

if (data[i].name == data[i - 1].name && data[i - 1].status == 1 && data[i].status == 0) {

custom[data[i - 1].name].push_back(data[i - 1]);

custom[data[i].name].push_back(data[i]);

}

for (auto it : custom) {

vector<node> temp = it.second;

cout << it.first;

printf(" %02d\n", temp[0].month);

double total = 0.0;

for (int i = 1; i < temp.size(); i += 2) {

double t = billFromZero(temp[i], rate) - billFromZero(temp[i - 1], rate);

printf("%02d:%02d:%02d %02d:%02d:%02d %d $%.2f\n", temp[i - 1].day, temp[i - 1].hour, temp[i - 1].minute, temp[i].day, temp[i].hour, temp[i].minute, temp[i].time - temp[i - 1].time, t);

total += t;

}

printf("Total amount: $%.2f\n", total);

}

return 0;

}

1021. Deepest Root (25)-PAT甲级真题（图的遍历，dfs，连通分量的个数）

A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=10000) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N-1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.

Output Specification:

For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print “Error: K components” where K is the number of connected components in the graph.

Sample Input 1:
5
1 2
1 3
1 4
2 5
Sample Output 1:
3
4
5
Sample Input 2:
5
1 3
1 4
2 5
3 4
Sample Output 2:
Error: 2 components
题目大意：给出n个结点（1~n）之间的n条边，问是否能构成一棵树，如果不能构成则输出它有的连通分量个数，如果能构成一棵树，输出能构成最深的树的高度时，树的根结点。如果有多个，按照从小到大输出。
分析：首先深度优先搜索判断它有几个连通分量。如果有多个，那就输出Error: x components，如果只有一个，就两次深度优先搜索，先从一个结点dfs后保留最高高度拥有的结点们，然后从这些结点中的其中任意一个开始dfs得到最高高度的结点们，这两个结点集合的并集就是所求

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int n, maxheight = 0;
vector<vector<int>> v;
bool visit[10010];
set<int> s;
vector<int> temp;
void dfs(int node, int height) {
    if(height > maxheight) {
        temp.clear();
        temp.push_back(node);
        maxheight = height;
    } else if(height == maxheight){
        temp.push_back(node);
    }
    visit[node] = true;
    for(int i = 0; i < v[node].size(); i++) {
        if(visit[v[node][i]] == false)
            dfs(v[node][i], height + 1);
    }
}
int main() {
    scanf("%d", &n);
    v.resize(n + 1);
    int a, b, cnt = 0, s1 = 0;
    for(int i = 0; i < n - 1; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) {
        if(visit[i] == false) {
            dfs(i, 1);
            if(i == 1) {
                if (temp.size() != 0) s1 = temp[0];
                for(int j = 0; j < temp.size(); j++)
                    s.insert(temp[j]);
            }
            cnt++;
        }
    }
    if(cnt >= 2) {
        printf("Error: %d components", cnt);
    } else {
        temp.clear();
        maxheight = 0;
        fill(visit, visit + 10010, false);
        dfs(s1, 1);
        for(int i = 0; i < temp.size(); i++)
            s.insert(temp[i]);
        for(auto it = s.begin(); it != s.end(); it++)
            printf("%d\n", *it);
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <set>

#include <algorithm>

using namespace std;

int n, maxheight = 0;

vector<vector<int>> v;

bool visit[10010];

set<int> s;

vector<int> temp;

void dfs(int node, int height) {

if(height > maxheight) {

temp.clear();

temp.push_back(node);

maxheight = height;

} else if(height == maxheight){

temp.push_back(node);

}

visit[node] = true;

for(int i = 0; i < v[node].size(); i++) {

if(visit[v[node][i]] == false)

dfs(v[node][i], height + 1);

}

int main() {

scanf("%d", &n);

v.resize(n + 1);

int a, b, cnt = 0, s1 = 0;

for(int i = 0; i < n - 1; i++) {

scanf("%d%d", &a, &b);

v[a].push_back(b);

v[b].push_back(a);

}

for(int i = 1; i <= n; i++) {

if(visit[i] == false) {

dfs(i, 1);

if(i == 1) {

if (temp.size() != 0) s1 = temp[0];

for(int j = 0; j < temp.size(); j++)

s.insert(temp[j]);

}

cnt++;

}

if(cnt >= 2) {

printf("Error: %d components", cnt);

} else {

temp.clear();

maxheight = 0;

fill(visit, visit + 10010, false);

dfs(s1, 1);

for(int i = 0; i < temp.size(); i++)

s.insert(temp[i]);

for(auto it = s.begin(); it != s.end(); it++)

printf("%d\n", *it);

}

return 0;

}