PAT – 第22页

1111. Online Map (30)-PAT甲级真题（Dijkstra + DFS）

Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (2 <= N <= 500), and M, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format:

V1 V2 one-way length time

where V1 and V2 are the indices (from 0 to N-1) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street.

Finally a pair of source and destination is given.

Output Specification:

For each case, first print the shortest path from the source to the destination with distance D in the format:

Distance = D: source -> v1 -> … -> destination

Then in the next line print the fastest path with total time T:

Time = T: source -> w1 -> … -> destination

In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.

In case the shortest and the fastest paths are identical, print them in one line in the format:

Distance = D; Time = T: source -> u1 -> … -> destination

Sample Input 1:
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5
Sample Output 1:
Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5
Sample Input 2:
7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5
Sample Output 2:
Distance = 3; Time = 4: 3 -> 2 -> 5

题目大意：给一张地图，两个结点中既有距离也有时间，有的单行有的双向，要求根据地图推荐两条路线：一条是最快到达路线，一条是最短距离的路线。
第一行给出两个整数N和M，表示地图中地点的个数和路径的条数。接下来的M行每一行给出：道路结点编号V1 道路结点编号V2 是否单行线道路长度所需时间
要求第一行输出最快到达时间Time和路径，第二行输出最短距离Distance和路径

分析：
1.用两个Dijkstra。一个求最短路径（如果相同求时间最短的那条），一个求最快路径（如果相同求结点数最小的那条）～～
2.求最短路径,和最快路径都可以在Dijkstra里面求前驱结点dispre和，Timepre数组～
3.dispre数组更新的条件是路径更短，或者路径相等的同时时间更短。
4.求最快路径时候要多维护一个NodeNum数组，记录在时间最短的情况下，到达此节点所需的节点数量。
Time数组更新的条件是，时间更短，时间相同的时候，如果此节点能让到达次节点是数目也变小，则更新Timepre，heNodeNum数组
5.最后根据dispre 和Timepre数组递归出两条路径，比较判断，输出最终答案～
注意：如果直接使用DFS的话，会导致最后一个测试用例“运行超时”～～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 999999999;
int dis[510], Time[510], e[510][510], w[510][510], dispre[510],Timepre[510], weight[510],NodeNum[510];
bool visit[510];
vector<int> dispath, Timepath, temppath;
int st, fin, minnode = inf;
void dfsdispath(int v) {
    dispath.push_back(v);
    if(v == st) return ;
    dfsdispath(dispre[v]);
}
void dfsTimepath(int v) {
    Timepath.push_back(v);
    if(v == st) return ;
    dfsTimepath(Timepre[v]);
}
int main() {
    fill(dis, dis + 510, inf);
    fill(Time, Time + 510, inf);
    fill(weight, weight + 510, inf);
    fill(e[0], e[0] + 510 * 510, inf);
    fill(w[0], w[0] + 510 * 510, inf);
    int n, m;
    scanf("%d %d", &n, &m);
    int a, b, flag, len, t;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d %d %d", &a, &b, &flag, &len, &t);
        e[a][b] = len;
        w[a][b] = t;
        if(flag != 1) {
            e[b][a] = len;
            w[b][a] = t;
        }
    }
    scanf("%d %d", &st, &fin);
    dis[st] = 0;
    for(int i = 0; i < n; i++)
        dispre[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) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(e[u][v] + dis[u] < dis[v]) {
                    dis[v] = e[u][v] + dis[u];
                    dispre[v] = u;
                    weight[v] = weight[u] + w[u][v];
                } else if(e[u][v] + dis[u] == dis[v] && weight[v] > weight[u] + w[u][v]) {
                    weight[v] = weight[u] + w[u][v];
                    dispre[v] = u;
                }
            }
        }
    }
    dfsdispath(fin);
    Time[st] = 0;
    fill(visit, visit + 510, false);
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && minn > Time[j]) {
                u = j;
                minn = Time[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && w[u][v] != inf) {
                if(w[u][v] + Time[u] < Time[v]) {
                    Time[v] = w[u][v] + Time[u];
                    Timepre[v]= u;
                    NodeNum[v]=NodeNum[u]+1;
                } else if(w[u][v] + Time[u] == Time[v]&&NodeNum[u]+1<NodeNum[v]) {
                    Timepre[v]= u;
                    NodeNum[v]=NodeNum[u]+1;
                }
            }
        }
    }
    dfsTimepath(fin);
    printf("Distance = %d", dis[fin]);
    if(dispath == Timepath) {
        printf("; Time = %d: ", Time[fin]);
    } else {
        printf(": ");
        for(int i = dispath.size() - 1; i >= 0; i--) {
            printf("%d", dispath[i]);
            if(i != 0) printf(" -> ");
        }
        printf("\nTime = %d: ", Time[fin]);
    }
    for(int i = Timepath.size() - 1; i >= 0; i--) {
        printf("%d", Timepath[i]);
        if(i != 0) printf(" -> ");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

const int inf = 999999999;

int dis[510], Time[510], e[510][510], w[510][510], dispre[510],Timepre[510], weight[510],NodeNum[510];

bool visit[510];

vector<int> dispath, Timepath, temppath;

int st, fin, minnode = inf;

void dfsdispath(int v) {

dispath.push_back(v);

if(v == st) return ;

dfsdispath(dispre[v]);

}

void dfsTimepath(int v) {

Timepath.push_back(v);

if(v == st) return ;

dfsTimepath(Timepre[v]);

}

int main() {

fill(dis, dis + 510, inf);

fill(Time, Time + 510, inf);

fill(weight, weight + 510, inf);

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

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

int n, m;

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

int a, b, flag, len, t;

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

scanf("%d %d %d %d %d", &a, &b, &flag, &len, &t);

e[a][b] = len;

w[a][b] = t;

if(flag != 1) {

e[b][a] = len;

w[b][a] = t;

}

scanf("%d %d", &st, &fin);

dis[st] = 0;

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

dispre[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) break;

visit[u] = true;

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

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

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

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

dispre[v] = u;

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

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

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

dispre[v] = u;

}

dfsdispath(fin);

Time[st] = 0;

fill(visit, visit + 510, false);

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

int u = -1, minn = inf;

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

if(visit[j] == false && minn > Time[j]) {

u = j;

minn = Time[j];

}

if(u == -1) break;

visit[u] = true;

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

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

if(w[u][v] + Time[u] < Time[v]) {

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

Timepre[v]= u;

NodeNum[v]=NodeNum[u]+1;

} else if(w[u][v] + Time[u] == Time[v]&&NodeNum[u]+1<NodeNum[v]) {

Timepre[v]= u;

NodeNum[v]=NodeNum[u]+1;

}

dfsTimepath(fin);

printf("Distance = %d", dis[fin]);

if(dispath == Timepath) {

printf("; Time = %d: ", Time[fin]);

} else {

printf(": ");

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

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

if(i != 0) printf(" -> ");

}

printf("\nTime = %d: ", Time[fin]);

}

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

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

if(i != 0) printf(" -> ");

}

return 0;

}

1087. All Roads Lead to Rome (30)-PAT甲级真题（Dijkstra + DFS）

Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.

Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<=N<=200), the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N-1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format “City1 City2 Cost”. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.

Output Specification:
For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommended. If such a route is still not unique, then we output the one with the maximum average happiness — it is guaranteed by the judge that such a solution exists and is unique.
Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommended route. Then in the next line, you are supposed to print the route in the format “City1->City2->…->ROM”.

Sample Input:
6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1
Sample Output:
3 3 195 97
HZH->PRS->ROM

题目大意：有N个城市，M条无向边，从某个给定的起始城市出发，前往名为ROM的城市。每个城市（除了起始城市）都有一个点权（称为幸福值），和边权（每条边所需的花费）。求从起点到ROM所需要的最少花费，并输出其路径。如果路径有多条，给出幸福值最大的那条。如果仍然不唯一，选择路径上的城市平均幸福值最大的那条路径
分析：Dijkstra+DFS。Dijkstra算出所有最短路径的路线pre二维数组，DFS求最大happiness的路径path，并求出路径条数，最大happiness，最大average～
注意：average是除去起点的average。城市名称可以用m存储字符串所对应的数字，用m2存储数字对应的字符串

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
const int inf = 999999999;
int e[205][205], weight[205], dis[205];
bool visit[205];
vector<int> pre[205], temppath, path;
map<string, int> m;
map<int, string> m2;
int maxvalue = 0, mindepth, cntpath = 0;
double maxavg;
void dfs(int v) {
    temppath.push_back(v);
    if(v == 1) {
        int value = 0;
        for(int i = 0; i < temppath.size(); i++) {
            value += weight[temppath[i]];
        }
        double tempavg = 1.0 * value / (temppath.size() - 1);
        if(value > maxvalue) {
            maxvalue = value;
            maxavg = tempavg;
            path = temppath;
        } else if(value == maxvalue && tempavg > maxavg) {
            maxavg = tempavg;
            path = temppath;
        }
        temppath.pop_back();
        cntpath++;
        return ;
    }
    for(int i = 0; i < pre[v].size(); i++) {
        dfs(pre[v][i]);
    }
    temppath.pop_back();
}
int main() {
    fill(e[0], e[0] + 205 * 205, inf);
    fill(dis, dis + 205, inf);
    scanf("%d %d", &n, &k);
    string s;
    cin >> s;
    m[s] = 1;
    m2[1] = s;
    for(int i = 1; i < n; i++) {
        cin >> s >> weight[i+1];
        m[s] = i+1;
        m2[i+1] = s;
    }
    string sa, sb;
    int temp;
    for(int i = 0; i < k; i++) {
        cin >> sa >> sb >> temp;
        e[m[sa]][m[sb]] = temp;
        e[m[sb]][m[sa]] = temp;
    }
    dis[1] = 0;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 1; 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 = 1; 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];
                    pre[v].clear();
                    pre[v].push_back(u);
                } else if(dis[v] == dis[u] + e[u][v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
    int rom = m["ROM"];
    dfs(rom);
    printf("%d %d %d %d\n", cntpath, dis[rom], maxvalue, (int)maxavg);
    for(int i = path.size() - 1; i >= 1; i--) {
        cout << m2[path[i]] << "->";
    }
    cout << "ROM";
    return 0;
}

#include <iostream>

#include <map>

#include <vector>

#include <algorithm>

using namespace std;

int n, k;

const int inf = 999999999;

int e[205][205], weight[205], dis[205];

bool visit[205];

vector<int> pre[205], temppath, path;

map<string, int> m;

map<int, string> m2;

int maxvalue = 0, mindepth, cntpath = 0;

double maxavg;

void dfs(int v) {

temppath.push_back(v);

if(v == 1) {

int value = 0;

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

value += weight[temppath[i]];

}

double tempavg = 1.0 * value / (temppath.size() - 1);

if(value > maxvalue) {

maxvalue = value;

maxavg = tempavg;

path = temppath;

} else if(value == maxvalue && tempavg > maxavg) {

maxavg = tempavg;

path = temppath;

}

temppath.pop_back();

cntpath++;

return ;

}

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

dfs(pre[v][i]);

}

temppath.pop_back();

}

int main() {

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

fill(dis, dis + 205, inf);

scanf("%d %d", &n, &k);

string s;

cin >> s;

m[s] = 1;

m2[1] = s;

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

cin >> s >> weight[i+1];

m[s] = i+1;

m2[i+1] = s;

}

string sa, sb;

int temp;

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

cin >> sa >> sb >> temp;

e[m[sa]][m[sb]] = temp;

e[m[sb]][m[sa]] = temp;

}

dis[1] = 0;

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

int u = -1, minn = inf;

for(int j = 1; 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 = 1; 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];

pre[v].clear();

pre[v].push_back(u);

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

pre[v].push_back(u);

}

int rom = m["ROM"];

dfs(rom);

printf("%d %d %d %d\n", cntpath, dis[rom], maxvalue, (int)maxavg);

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

cout << m2[path[i]] << "->";

}

cout << "ROM";

return 0;

}

L1-015. 跟奥巴马一起画方块-PAT团体程序设计天梯赛GPLT

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！
输入格式：
输入在一行中给出正方形边长N（3<=N<=21）和组成正方形边的某种字符C，间隔一个空格。
输出格式：
输出由给定字符C画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的50%（四舍五入取整）。
输入样例：
10 a
输出样例：
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa

#include <iostream>
using namespace std;
int main() {
    int N;
    cin >> N;
    char c;
    cin >> c;
    int t = N / 2 + N % 2;
    for (int i = 0; i < t - 1; i++) {
        for (int k = 0; k < N; k++)
            cout << c;
        cout << endl;
    }
    for (int i = 0; i < N; i++)
        cout << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int N;

cin >> N;

char c;

cin >> c;

int t = N / 2 + N % 2;

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

for (int k = 0; k < N; k++)

cout << c;

cout << endl;

}

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

cout << c;

return 0;

}

L3-005. 垃圾箱分布-PAT团体程序设计天梯赛GPLT（Dijkstra）

大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。

现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。

输入格式：

输入第一行给出4个正整数：N（<= 103）是居民点的个数；M（<= 10）是垃圾箱候选地点的个数；K（<= 104）是居民点和垃圾箱候选地点之间的道路的条数；DS是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从1到N编号，所有的垃圾箱候选地点从G1到GM编号。

随后K行，每行按下列格式描述一条道路：
P1 P2 Dist
其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。

输出格式：

首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出“No Solution”。

输入样例1：
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
输出样例1：
G1
2.0 3.3
输入样例2：
2 1 2 10
1 G1 9
2 G1 20
输出样例2：
No Solution

题目大意：从m个垃圾站里面选取1个站点，让他离居民区的最近的人最远，并且没有超出服务范围ds之内。如果有很多个最远的垃圾站，输出距离所有居民区距离平均值最小的那个。如果平均值还是一样，就输出按照顺序排列垃圾站编号最小的那个、
分析：
因为垃圾站之间也是彼此有路连接的，所以最短路径计算的时候也要把垃圾站算上。所以我们就是堆n+m个点进行Dijkstra计算最短路径。要求计算出1~m号垃圾站距离其他站点的最短路径。这时候可以遍历dis数组，如果dis存在一个距离大于服务范围ds的距离，那么我们就舍弃这个垃圾站。取最最短的路径，这就是距离它最近的垃圾站mindis。如果mindis > ansdis，就是说找到了一个距离居民最小距离的垃圾站是更远的，那就选这个垃圾站，更新ansid为它的id。最后输出
对于垃圾站的字符串编号的处理：如果最近居民区最大的值没有变化但是找到了一个更小的平均距离，那就选这个。我们可以根据输入的是G还是数字，如果是数字就令编号为他自己，如果是G开头的，编号设为n+G后面的数字。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int inf = 999999999;
int n, m, k, ds, station;
int e[1020][1020], dis[1020];
bool visit[1020];
int main() {
    fill(e[0], e[0] + 1020 * 1020, inf);
    fill(dis, dis + 1020, inf);
    scanf("%d%d%d%d", &n, &m, &k, &ds);
    for(int i = 0; i < k; i++) {
        int tempdis;
        string s, t;
        cin >> s >> t >> tempdis;
        int a, b;
        if(s[0] == 'G') {
            s = s.substr(1);
            a = n + stoi(s);
        } else {
            a = stoi(s);
        }
        if(t[0] == 'G') {
            t = t.substr(1);
            b = n + stoi(t);
        } else {
            b = stoi(t);
        }
        e[a][b] = tempdis;
        e[b][a] = tempdis;
    }
    int ansid = -1;
    double ansdis = -1, ansaver = inf;
    for(int index = n + 1; index <= n + m; index++) {
        double mindis = inf, aver = 0;
        fill(dis, dis + 1020, inf);
        fill(visit, visit + 1020, false);
        dis[index] = 0;
        for(int i = 0; i < n + m; i++) {
            int u = -1, minn = inf;
            for(int j = 1; j <= n + m; j++) {
                if(visit[j] == false && dis[j] < minn) {
                    u = j;
                    minn = dis[j];
                }
            }
            if(u == -1) break;
            visit[u] = true;
            for(int v = 1; v <= n + m; v++) {
                if(visit[v] == false && dis[v] > dis[u] + e[u][v])
                    dis[v] = dis[u] + e[u][v];
            }
        }
        for(int i = 1; i <= n; i++) {
            if(dis[i] > ds) {
                mindis = -1;
                break;
            }
            if(dis[i] < mindis) mindis = dis[i];
            aver += 1.0 * dis[i];
        }
        if(mindis == -1) continue;
        aver = aver / n;
        if(mindis > ansdis) {
            ansid = index;
            ansdis = mindis;
            ansaver = aver;
        } else if(mindis == ansdis && aver < ansaver) {
            ansid = index;
            ansaver = aver;
        }
    }
    if(ansid == -1)
        printf("No Solution");
    else {
        printf("G%d\n", ansid - n);
        printf("%.1f %.1f", ansdis, ansaver);
    }
    return 0;
}

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <string>

using namespace std;

const int inf = 999999999;

int n, m, k, ds, station;

int e[1020][1020], dis[1020];

bool visit[1020];

int main() {

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

fill(dis, dis + 1020, inf);

scanf("%d%d%d%d", &n, &m, &k, &ds);

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

int tempdis;

string s, t;

cin >> s >> t >> tempdis;

int a, b;

if(s[0] == 'G') {

s = s.substr(1);

a = n + stoi(s);

} else {

a = stoi(s);

}

if(t[0] == 'G') {

t = t.substr(1);

b = n + stoi(t);

} else {

b = stoi(t);

}

e[a][b] = tempdis;

e[b][a] = tempdis;

}

int ansid = -1;

double ansdis = -1, ansaver = inf;

for(int index = n + 1; index <= n + m; index++) {

double mindis = inf, aver = 0;

fill(dis, dis + 1020, inf);

fill(visit, visit + 1020, false);

dis[index] = 0;

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

int u = -1, minn = inf;

for(int j = 1; j <= n + m; j++) {

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

u = j;

minn = dis[j];

}

if(u == -1) break;

visit[u] = true;

for(int v = 1; v <= n + m; v++) {

if(visit[v] == false && dis[v] > dis[u] + e[u][v])

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

}

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

if(dis[i] > ds) {

mindis = -1;

break;

}

if(dis[i] < mindis) mindis = dis[i];

aver += 1.0 * dis[i];

}

if(mindis == -1) continue;

aver = aver / n;

if(mindis > ansdis) {

ansid = index;

ansdis = mindis;

ansaver = aver;

} else if(mindis == ansdis && aver < ansaver) {

ansid = index;

ansaver = aver;

}

if(ansid == -1)

printf("No Solution");

else {

printf("G%d\n", ansid - n);

printf("%.1f %.1f", ansdis, ansaver);

}

return 0;

}

1072. Gas Station (30)-PAT甲级真题（Dijkstra）

A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range.

Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendation. If there are more than one solution, output the one with the smallest average distance to all the houses. If such a solution is still not unique, output the one with the smallest index number.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive integers: N (<= 103), the total number of houses; M (<= 10), the total number of the candidate locations for the gas stations; K (<= 104), the number of roads connecting the houses and the gas stations; and DS, the maximum service range of the gas station. It is hence assumed that all the houses are numbered from 1 to N, and all the candidate locations are numbered from G1 to GM.

Then K lines follow, each describes a road in the format
P1 P2 Dist
where P1 and P2 are the two ends of a road which can be either house numbers or gas station numbers, and Dist is the integer length of the road.

Output Specification:

For each test case, print in the first line the index number of the best location. In the next line, print the minimum and the average distances between the solution and all the houses. The numbers in a line must be separated by a space and be accurate up to 1 decimal place. If the solution does not exist, simply output “No Solution”.

Sample Input 1:
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
Sample Output 1:
G1
2.0 3.3
Sample Input 2:
2 1 2 10
1 G1 9
2 G1 20
Sample Output 2:
No Solution

题目大意：从m个加油站里面选取1个站点，让他离居民区的最近的人最远，并且没有超出服务范围ds之内。如果有很多个最远的加油站，输出距离所有居民区距离平均值最小的那个。如果平均值还是一样，就输出按照顺序排列加油站编号最小的那个
分析：
因为加油站之间也是彼此有路连接的，所以最短路径计算的时候也要把加油站算上。所以我们就是对n+m个点进行Dijkstra计算最短路径。要求计算出1~m号加油站距离其他站点的最短路径。这时候可以遍历dis数组，如果dis存在一个距离大于服务范围ds的距离，那么我们就舍弃这个加油站。取最最短的路径，这就是距离它最近的加油站mindis。如果mindis > ansdis，就是说找到了一个距离居民最小距离的加油站是更远的，那就选这个加油站，更新ansid为它的id。最后输出
对于加油站的字符串编号的处理：如果最近居民区最大的值没有变化但是找到了一个更小的平均距离，那就选这个。我们可以根据输入的是G还是数字，如果是数字就令编号为他自己，如果是G开头的，编号设为n+G后面的数字。
Update：Github用户littlesevenmo在issue中提出需要添加输入判断，题目中并没有说明两点之间最多只有一条路。也就是说，有可能两点之间有多条路，因此需要添加判断，只存储距离最短的路。另外，也有可能会出现 G1 G1 9999这样的测试数据，因此，自身与自身之间的距离要初始化为0。完善后的代码如下：

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int inf = 999999999;
int n, m, k, ds, station;
int e[1020][1020], dis[1020];
bool visit[1020];
int main() {
    fill(e[0], e[0] + 1020 * 1020, inf);
    for (int i = 0; i < 1020; i++) e[i][i] = 0;
    fill(dis, dis + 1020, inf);
    scanf("%d%d%d%d", &n, &m, &k, &ds);
    string s, t;
    for (int i = 0; i < k; i++) {
        int tempdis;
        cin >> s >> t >> tempdis;
        int a, b;
        if (s[0] == 'G') {
            s = s.substr(1);
            a = n + stoi(s);
        } else {
            a = stoi(s);
        }
        if (t[0] == 'G') {
            t = t.substr(1);
            b = n + stoi(t);
        } else {
            b = stoi(t);
        }
        e[a][b] = e[b][a] = min(tempdis, e[a][b]);
    }
    int ansid = -1;
    double ansdis = -1, ansaver = inf;
    for (int index = n + 1; index <= n + m; index++) {
        double mindis = inf, aver = 0;
        fill(dis, dis + 1020, inf);
        fill(visit, visit + 1020, false);
        dis[index] = 0;
        for (int i = 0; i < n + m; i++) {
            int u = -1, minn = inf;
            for (int j = 1; j <= n + m; j++) {
                if (visit[j] == false && dis[j] < minn) {
                    u = j;
                    minn = dis[j];
                }
            }
            if (u == -1) break;
            visit[u] = true;
            for (int v = 1; v <= n + m; v++) {
                if (visit[v] == false && dis[v] > dis[u] + e[u][v])
                    dis[v] = dis[u] + e[u][v];
            }
        }
        for (int i = 1; i <= n; i++) {
            if (dis[i] > ds) {
                mindis = -1;
                break;
            }
            if (dis[i] < mindis) mindis = dis[i];
            aver += 1.0 * dis[i];
        }
        if (mindis == -1) continue;
        aver = aver / n;
        if (mindis > ansdis) {
            ansid = index;
            ansdis = mindis;
            ansaver = aver;
        } else if (mindis == ansdis && aver < ansaver) {
            ansid = index;
            ansaver = aver;
        }
    }
    if (ansid == -1)
        printf("No Solution");
    else
        printf("G%d\n%.1f %.1f", ansid - n, ansdis, ansaver);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

const int inf = 999999999;

int n, m, k, ds, station;

int e[1020][1020], dis[1020];

bool visit[1020];

int main() {

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

for (int i = 0; i < 1020; i++) e[i][i] = 0;

fill(dis, dis + 1020, inf);

scanf("%d%d%d%d", &n, &m, &k, &ds);

string s, t;

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

int tempdis;

cin >> s >> t >> tempdis;

int a, b;

if (s[0] == 'G') {

s = s.substr(1);

a = n + stoi(s);

} else {

a = stoi(s);

}

if (t[0] == 'G') {

t = t.substr(1);

b = n + stoi(t);

} else {

b = stoi(t);

}

e[a][b] = e[b][a] = min(tempdis, e[a][b]);

}

int ansid = -1;

double ansdis = -1, ansaver = inf;

for (int index = n + 1; index <= n + m; index++) {

double mindis = inf, aver = 0;

fill(dis, dis + 1020, inf);

fill(visit, visit + 1020, false);

dis[index] = 0;

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

int u = -1, minn = inf;

for (int j = 1; j <= n + m; j++) {

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

u = j;

minn = dis[j];

}

if (u == -1) break;

visit[u] = true;

for (int v = 1; v <= n + m; v++) {

if (visit[v] == false && dis[v] > dis[u] + e[u][v])

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

}

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

if (dis[i] > ds) {

mindis = -1;

break;

}

if (dis[i] < mindis) mindis = dis[i];

aver += 1.0 * dis[i];

}

if (mindis == -1) continue;

aver = aver / n;

if (mindis > ansdis) {

ansid = index;

ansdis = mindis;

ansaver = aver;

} else if (mindis == ansdis && aver < ansaver) {

ansid = index;

ansaver = aver;

}

if (ansid == -1)

printf("No Solution");

else

printf("G%d\n%.1f %.1f", ansid - n, ansdis, ansaver);

return 0;

}

1030. Travel Plan (30)-PAT甲级真题（Dijkstra + DFS，输出路径，边权）

A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (<=500) is the number of cities (and hence the cities are numbered from 0 to N-1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:

City1 City2 Distance Cost

where the numbers are all integers no more than 500, and are separated by a space.

Output Specification:

For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.

Sample Input
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
Sample Output
0 2 3 3 40
题目大意：求起点到终点的最短路径最短距离和花费，要求首先路径最短，其次花费最少，要输出完整路径
分析：Dijksta + DFS。 Dijkstra记录路径pre数组，然后用dfs求最短的一条mincost以及它的路径path，最后输出path数组和mincost
注意路径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) {
    temppath.push_back(v);
    if(v == s) {
        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 ;
    }
    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 = 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[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;
}

#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) {

temppath.push_back(v);

if(v == s) {

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 ;

}

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 = 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[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;

}