题目：略。
解答：今天（2018/8/29）我将迪杰斯特拉算法复习了下，收获良多，然后将其用邻接矩阵和邻接链表都实现了下，今晚刷了PAT甲级中的1072 Gas Station（30 分）、1003 Emergency（25 分）和1030 Travel Plan（30 分），都是最短路径问题，其中1072题应该是比较烦的了，花的时间也比较久，但思路都相同，dijkstra算法的实现在我另一篇博客中Disjkstra最短路径-算法题总结进行了分析。
今天（2018/8/30）在PAT上又找到一道相似的题目1087 All Roads Lead to Rome（30 分），也是用dijkstra算法实现，比较满意。
这四题的AC代码如下：
1003题AC代码：
/*1003题，用邻接链表实现*/
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>#define maxn 510
#define inf 100000000
using namespace std;typedef struct{int v, dis;
}node;int n, m, c1, c2;
vector<node> e[maxn];
int dis[maxn];
bool visited[maxn] = { false };
int weight[maxn]; //记录各点的点权
int w[maxn]; //记录各点的累积最大点权
int num[maxn]; //记录最短路径的数量void dijkstra(int s)
{dis[s] = 0; num[s] = 1;for (int i = 0; i < n; ++i){int u = -1, mindis = inf;for (int j = 0; j < n; ++j){if (visited[j] == false && mindis > dis[j]){mindis = dis[j];u = j;}}if (u == -1) return;visited[u] = true;for (int k = 0; k < e[u].size(); ++k){int v = e[u][k].v;if (dis[u] + e[u][k].dis < dis[v]){dis[v] = dis[u] + e[u][k].dis;num[v] = num[u];w[v] = w[u] + weight[v];}else if (dis[u] + e[u][k].dis == dis[v]){num[v] += num[u];if (w[v] < w[u] + weight[v]){w[v] = w[u] + weight[v];}}}}
}int main()
{cin >> n >> m >> c1 >> c2;fill(dis, dis + maxn, inf);for (int i = 0; i < n; ++i){cin >> weight[i];w[i] = weight[i];}for (int i = 0; i < m; ++i){int v1, v2, d;node tmp;cin >> v1 >> v2 >> d;tmp.dis = d; tmp.v = v1;e[v2].push_back(tmp);tmp.v = v2;e[v1].push_back(tmp);}dijkstra(c1);cout << num[c2] << " " << w[c2] << endl;return 0;
}1030题AC代码:
#include<cstdio>
#include<iostream>
#include<vector>#define inf 1000
#define maxn 510using namespace std;typedef struct{int v, dis, cost;
}node;int n, m, s, d;
int dis[maxn];
bool visited[maxn] = { false };
int tcost[maxn];
int pre[maxn];
vector<node> e[maxn];void disjkstra(int s)
{dis[s] = 0; tcost[s] = 0;for (int i = 0; i < n; ++i){int u = -1, mindis = inf;for (int j = 0; j < n; ++j){if (visited[j] == false && dis[j] < mindis){mindis = dis[j];u = j;}}if (u == -1) return;visited[u] = true;for (int k = 0; k < e[u].size(); ++k){int v = e[u][k].v;//输出//cout << v << endl;if (visited[v] == false){if (dis[u] + e[u][k].dis < dis[v]){dis[v] = dis[u] + e[u][k].dis;pre[v] = u;tcost[v] = tcost[u] + e[u][k].cost;}else if (dis[u] + e[u][k].dis == dis[v] && tcost[v] > tcost[u] + e[u][k].cost){pre[v] = u;tcost[v] = tcost[u] + e[u][k].cost;}}}// cout << endl;}
}void dfs(int s, int d){if (s == d){printf("%d ", s);return;}dfs(s, pre[d]);printf("%d ", d);}
int main(){cin >> n >> m >> s >> d;fill(dis, dis + maxn, inf);fill(dis, dis + maxn, inf);for (int i = 0; i < n; ++i) pre[i] = i;for (int i = 0; i < m; ++i){int v1, v2, distance, cost;node tmp;cin >> v1 >> v2 >> distance >> cost;tmp.v = v2; tmp.dis = distance; tmp.cost = cost;e[v1].push_back(tmp);tmp.v = v1;e[v2].push_back(tmp);}disjkstra(s);//输出路径dfs(s, d);//输出最短路径cout << dis[d] << " ";//输出最小花费cout << tcost[d] << endl;return 0;
}
1072题代码：
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<sstream>#define maxn 1015
#define inf 100000000
using namespace std;typedef struct{int v, dis;
}node;int n, m, k, d;vector<node> e[maxn];
int dis[maxn];
bool visited[maxn] = { false };int getseq(const string& s)
{stringstream ss;int seq;if (s.front() != 'G'){ss.str(s);ss >> seq;return seq;}else{ss.str(s.substr(1));ss >> seq;//cout << "seq:" << seq << endl;return (seq + n);}
}void dijkstra(int s)
{dis[s] = 0;for (int i = 0; i < n+m; ++i){int u = -1, mindis = inf;for (int j = 1; j <= n+m; ++j){if (visited[j] == false && mindis > dis[j]){u = j;mindis = dis[j];}}if (u == -1) return;visited[u] = true;for (int j = 0; j < e[u].size(); ++j){int v = e[u][j].v;if (visited[v] == false && dis[v] > dis[u] + e[u][j].dis){dis[v] = dis[u] + e[u][j].dis;}}}
}
int main()
{cin >> n >> m >> k >> d;for (int i = 0; i < k; ++i){string id1, id2; int distance;cin >> id1 >> id2 >> distance;int v1 = getseq(id1), v2 = getseq(id2);//cout << v1 << " " << v2 << " " << distance;node tmp; tmp.dis = distance; tmp.v = v2;e[v1].push_back(tmp);tmp.v = v1;e[v2].push_back(tmp);}int flag = false; //记录是否有方案int gas = n;double mindis = 0, tdis = 0, avgdis = inf;for (int s = n + 1; s <= n + m; ++s){fill(visited, visited + maxn, 0);/*for (int r = n + 1; r <= n + m; ++r){if (r != s) visited[r] = true;}*/fill(dis, dis + maxn, inf);dijkstra(s);//输出结果/*for (int i = 1; i <= n + m; ++i){cout << dis[i] << " ";}*///cout << endl;//判断距离是否都在范围内bool isok = true;double tmp_tdis = 0, tmp_avgdis = inf, tmp_mindis = inf;for (int i = 1; i <= n; ++i){tmp_tdis += dis[i];tmp_mindis = tmp_mindis > dis[i] ? dis[i] : tmp_mindis;if (dis[i] > d){isok = false; break;}}if (isok == false) continue;//将最小平均距离的gas station记录下来tmp_avgdis = tmp_tdis / n;//cout << tmp_tdis << " " << tmp_mindis << endl;if (tmp_mindis > mindis){avgdis = tmp_avgdis;mindis = tmp_mindis;gas = s - n;flag = true;}else if (tmp_mindis == mindis && tmp_avgdis < avgdis){avgdis = tmp_avgdis;mindis = tmp_mindis;gas = s - n;flag = true;}//cout << avgdis << " " << mindis << endl;}if (flag == true){cout << 'G' << gas << endl;printf("%.1f %.1f\n", mindis, avgdis);}else{printf("No Solution\n");}return 0;
}1087题AC代码如下：
#include<iostream>
#include<vector>
#include<string>#define maxn 220
#define inf 1000000using namespace std;typedef struct{int v, dis;
}node;int dis[maxn];
int happy[maxn];
bool visited[maxn] = { false };
int pre[maxn];
vector<node> e[maxn];
vector<string> names;
int h[maxn];
int num[maxn];int n, k;int getIndex(const string& name)
{for (int i = 0; i < names.size(); ++i){if (names[i] == name) return i;}return -1;
}void dijkstra(int s)
{dis[s] = 0; num[s] = 1;for (int i = 0; i < n; ++i){int u = -1, mindis = inf;for (int j = 0; j < n; ++j){if (visited[j] == false && mindis > dis[j]){u = j;mindis = dis[j];}}if (u == -1) return;visited[u] = true;for (int p = 0; p < e[u].size(); ++p){int v = e[u][p].v;if (visited[v] == false){if (dis[v] > dis[u] + e[u][p].dis){dis[v] = dis[u] + e[u][p].dis;h[v] = h[u] + happy[v];pre[v] = u;num[v] = num[u];}else if (dis[v] == dis[u] + e[u][p].dis){if (h[v] < h[u] + happy[v]){h[v] = h[u] + happy[v];pre[v] = u;}num[v] += num[u];}}}}
}void dfs(int s, int v)
{if (s == v){cout << names[s] << "->";return;}dfs(s, pre[v]);if(names[v] == "ROM") cout << names[v];else cout << names[v] << "->";
}void dfs_count(int s, int v, int& count)
{if (s == v){return;}dfs_count(s, pre[v], ++count);
}
int main()
{string start;cin >> n >> k >> start;names.push_back(start); happy[0] = 0;for (int i = 1; i <= n - 1; ++i){string v; int happies;cin >> v >> happies;names.push_back(v); happy[i] = happies;}//初始化h数组fill(h, h + maxn, 0);//初始化dis数组fill(dis, dis + maxn, inf);//初始化num数组fill(num, num + maxn, 0);//记录路径for (int i = 0; i < k; ++i){string v1, v2; int d;cin >> v1 >> v2 >> d;int iv1 = getIndex(v1), iv2 = getIndex(v2);node tmp; tmp.dis = d;tmp.v = iv1;e[iv2].push_back(tmp);tmp.v = iv2;e[iv1].push_back(tmp);}int s = getIndex(start);dijkstra(s);//输出结果int count = 0;int v = getIndex("ROM");cout << num[v] << " " << dis[v] << " " << h[v] << " ";dfs_count(s, v, count);cout << h[v] / count << endl;dfs(s, v);return 0;
}