USB迷 | 专注于互联网分享

    最新消息： USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。
    你的位置： 首页 > 互联网 > 【PAT甲级 单源最短路径】1087 All Roads Lead to Rome (30 分)

    【PAT甲级 单源最短路径】1087 All Roads Lead to Rome (30 分)

    互联网 admin 4浏览 0评论

    【PAT甲级 单源最短路径】1087 All Roads Lead to Rome (30 分)

    字符串索引图，使用了map映射，用了一些不常用的知识，能这么写出来很开心

    这么写可以使得map的默认值为INF而不是值初始化的0

    
struct defaultCost{int cost;defaultCost():cost(INF){}; // 更改不存在key的map的默认value值为INFdefaultCost(int c):cost(c){}
};
map<string, defaultCost> cost; // 之前的dist数组，改名了

    当点的编号不是数字而是字符串的时候使用map是个不错的方法

    map<string, vector<Node> > G;  // 边权
map<string, int> V;    // 点权
map<string, defaultCost> cost; // 之前的dist数组，改名了
map<string, bool> vis;
map<string, vector<string>> pre;

    Dijkstra + DFS

    # include <iostream>
# include <algorithm>
# include <vector>
# include <map>
using namespace std;const int MAXV = 210;
const int INF  = 0xffffff;struct Node{string name;int cost;
};
// 设一个结构体并赋予初值就可以设定访问map不存在的key时的默认value值
struct defaultCost{int cost;defaultCost():cost(INF){}; // 更改不存在key的map的默认value值为INFdefaultCost(int c):cost(c){}
};map<string, vector<Node> > G;  // 边权
map<string, int> V;    // 点权
map<string, defaultCost> cost; // 之前的dist数组，改名了
map<string, bool> vis;
map<string, vector<string>> pre;int N, K;
string st, ed = "ROM";void Dijsktra(string s){cost[s] = 0;for(int i = 0;i < N;++i){string u = "000";int MIN = INF;for(auto p: V){string j = p.first;if(vis[j] == false && cost[j].cost < MIN){u = j;MIN = cost[j].cost;}}if(u == "000") return;vis[u] = true;for(Node next: G[u]){string v = next.name;int uv_cost = next.cost;if(vis[v] == false){if(cost[u].cost + uv_cost  < cost[v].cost){cost[v].cost = cost[u].cost + uv_cost;pre[v].clear();pre[v].push_back(u);} elseif(cost[u].cost + uv_cost == cost[v].cost){pre[v].push_back(u);}}}}}vector<string> path, tempPath;
int routes = 0; // 相等cost的路径数量
int maxSumHappyness = -1; // 最大快乐值;
double maxAvgHappyness = -1; // 最大平均快乐值
void DFS(string v){if(v == st){routes++;tempPath.push_back(st);int sumhappyness = 0;double avghappyness = 0.0;for(string id: tempPath){sumhappyness += V[id];} avghappyness = sumhappyness / (tempPath.size() - 1);if(sumhappyness > maxSumHappyness){maxSumHappyness = sumhappyness;maxAvgHappyness = avghappyness;path = tempPath;}elseif(sumhappyness == maxSumHappyness){if(avghappyness > maxAvgHappyness){maxAvgHappyness = avghappyness;path = tempPath;  }}tempPath.pop_back();return;}tempPath.push_back(v);for(string u: pre[v]){DFS(u);}tempPath.pop_back();
}int main(){cin >> N >> K >> st;for(int i = 0;i < N-1;++i){ // 不输入起点的开心值，所以要N-1，并且给起点得到开心值初始化为0（被坑了）string city; int happy;cin >> city >> happy;V[city] = happy;}V[st] = 0;for(int i = 0;i < K;++i){string city1, city2; int cost;cin >> city1 >> city2 >> cost;G[city1].push_back({city2, cost});G[city2].push_back({city1, cost});}Dijsktra(st);DFS(ed);printf("%d %d %d %.0f\n",routes, cost[ed].cost, maxSumHappyness, maxAvgHappyness);for(int i = path.size() - 1;i >= 0;--i){cout << path[i];if(i != 0) cout << "->";else cout << "\n";}return 0;
}

    使用优先队列优化

    # include <iostream>
# include <algorithm>
# include <vector>
# include <map>
# include <unordered_map>
# include <queue>using namespace std;const int MAXV = 210;
const int INF  = 0xffffff;struct Node{string name;int cost;
};
// 设一个结构体并赋予初值就可以设定访问map不存在的key时的默认value值
struct defaultCost{int cost;defaultCost():cost(INF){}; // 记得添上一个默认函数（优先队列优化时这个还是必要的）defaultCost(int c):cost(c){}
};map<string, vector<Node> > G;  // 边权
map<string, int> V;    // 点权
map<string, defaultCost> cost; // 之前的dist数组，改名了
// map<string, bool> vis; // 优先队列优化时不需要visit数组
map<string, vector<string>> pre;// first是起点到second点的距离，second是顶点的名字
typedef pair<int, string> Pair; 
// 使用优先级队列，因为pair有比较运算，所以可直接传入
priority_queue<Pair, vector<Pair>, greater<Pair>> Q; int N, K;
string st, ed = "ROM";void Dijsktra(string s){cost[s] = 0;Q.push({cost[s].cost, s}); // push入起点while(!Q.empty()){Pair p = Q.top();Q.pop();string u = p.second;if(cost[u].cost < p.first) continue;for(Node next: G[u]){string v = next.name;int uv_cost = next.cost;if(cost[u].cost + uv_cost  < cost[v].cost){cost[v].cost = cost[u].cost + uv_cost;Q.push({cost[v].cost ,v}); // push入更短的Pairpre[v].clear();pre[v].push_back(u);} elseif(cost[u].cost + uv_cost == cost[v].cost){pre[v].push_back(u);}}}}vector<string> path, tempPath;
int routes = 0; // 相等cost的路径数量
int maxSumHappyness = -1; // 最大快乐值;
double maxAvgHappyness = -1; // 平均快乐值
void DFS(string v){if(v == st){routes++;tempPath.push_back(st);int sumhappyness = 0;double avghappyness = 0.0;for(string id: tempPath){sumhappyness += V[id];} avghappyness = sumhappyness / (tempPath.size() - 1);if(sumhappyness > maxSumHappyness){maxSumHappyness = sumhappyness;maxAvgHappyness = avghappyness;path = tempPath;}elseif(sumhappyness == maxSumHappyness){if(avghappyness > maxAvgHappyness){maxAvgHappyness = avghappyness;path = tempPath;  }}tempPath.pop_back();return;}tempPath.push_back(v);for(string u: pre[v]){DFS(u);}tempPath.pop_back();
}int main(){cin >> N >> K >> st;for(int i = 0;i < N-1;++i){ // 不输入起点的开心值，所以要N-1，并且给起点得到开心值初始化为0（被坑了）string city; int happy;cin >> city >> happy;V[city] = happy;}V[st] = 0;for(int i = 0;i < K;++i){string city1, city2; int cost;cin >> city1 >> city2 >> cost;G[city1].push_back({city2, cost});G[city2].push_back({city1, cost});}Dijsktra(st);DFS(ed);printf("%d %d %d %.0f\n",routes, cost[ed].cost, maxSumHappyness, maxAvgHappyness);for(int i = path.size() - 1;i >= 0;--i){cout << path[i];if(i != 0) cout << "->";else cout << "\n";}return 0;
}

    【PAT甲级 单源最短路径】1087 All Roads Lead to Rome (30 分)

    字符串索引图，使用了map映射，用了一些不常用的知识，能这么写出来很开心

    这么写可以使得map的默认值为INF而不是值初始化的0

    
struct defaultCost{int cost;defaultCost():cost(INF){}; // 更改不存在key的map的默认value值为INFdefaultCost(int c):cost(c){}
};
map<string, defaultCost> cost; // 之前的dist数组，改名了

    当点的编号不是数字而是字符串的时候使用map是个不错的方法

    map<string, vector<Node> > G;  // 边权
map<string, int> V;    // 点权
map<string, defaultCost> cost; // 之前的dist数组，改名了
map<string, bool> vis;
map<string, vector<string>> pre;

    Dijkstra + DFS

    # include <iostream>
# include <algorithm>
# include <vector>
# include <map>
using namespace std;const int MAXV = 210;
const int INF  = 0xffffff;struct Node{string name;int cost;
};
// 设一个结构体并赋予初值就可以设定访问map不存在的key时的默认value值
struct defaultCost{int cost;defaultCost():cost(INF){}; // 更改不存在key的map的默认value值为INFdefaultCost(int c):cost(c){}
};map<string, vector<Node> > G;  // 边权
map<string, int> V;    // 点权
map<string, defaultCost> cost; // 之前的dist数组，改名了
map<string, bool> vis;
map<string, vector<string>> pre;int N, K;
string st, ed = "ROM";void Dijsktra(string s){cost[s] = 0;for(int i = 0;i < N;++i){string u = "000";int MIN = INF;for(auto p: V){string j = p.first;if(vis[j] == false && cost[j].cost < MIN){u = j;MIN = cost[j].cost;}}if(u == "000") return;vis[u] = true;for(Node next: G[u]){string v = next.name;int uv_cost = next.cost;if(vis[v] == false){if(cost[u].cost + uv_cost  < cost[v].cost){cost[v].cost = cost[u].cost + uv_cost;pre[v].clear();pre[v].push_back(u);} elseif(cost[u].cost + uv_cost == cost[v].cost){pre[v].push_back(u);}}}}}vector<string> path, tempPath;
int routes = 0; // 相等cost的路径数量
int maxSumHappyness = -1; // 最大快乐值;
double maxAvgHappyness = -1; // 最大平均快乐值
void DFS(string v){if(v == st){routes++;tempPath.push_back(st);int sumhappyness = 0;double avghappyness = 0.0;for(string id: tempPath){sumhappyness += V[id];} avghappyness = sumhappyness / (tempPath.size() - 1);if(sumhappyness > maxSumHappyness){maxSumHappyness = sumhappyness;maxAvgHappyness = avghappyness;path = tempPath;}elseif(sumhappyness == maxSumHappyness){if(avghappyness > maxAvgHappyness){maxAvgHappyness = avghappyness;path = tempPath;  }}tempPath.pop_back();return;}tempPath.push_back(v);for(string u: pre[v]){DFS(u);}tempPath.pop_back();
}int main(){cin >> N >> K >> st;for(int i = 0;i < N-1;++i){ // 不输入起点的开心值，所以要N-1，并且给起点得到开心值初始化为0（被坑了）string city; int happy;cin >> city >> happy;V[city] = happy;}V[st] = 0;for(int i = 0;i < K;++i){string city1, city2; int cost;cin >> city1 >> city2 >> cost;G[city1].push_back({city2, cost});G[city2].push_back({city1, cost});}Dijsktra(st);DFS(ed);printf("%d %d %d %.0f\n",routes, cost[ed].cost, maxSumHappyness, maxAvgHappyness);for(int i = path.size() - 1;i >= 0;--i){cout << path[i];if(i != 0) cout << "->";else cout << "\n";}return 0;
}

    使用优先队列优化

    # include <iostream>
# include <algorithm>
# include <vector>
# include <map>
# include <unordered_map>
# include <queue>using namespace std;const int MAXV = 210;
const int INF  = 0xffffff;struct Node{string name;int cost;
};
// 设一个结构体并赋予初值就可以设定访问map不存在的key时的默认value值
struct defaultCost{int cost;defaultCost():cost(INF){}; // 记得添上一个默认函数（优先队列优化时这个还是必要的）defaultCost(int c):cost(c){}
};map<string, vector<Node> > G;  // 边权
map<string, int> V;    // 点权
map<string, defaultCost> cost; // 之前的dist数组，改名了
// map<string, bool> vis; // 优先队列优化时不需要visit数组
map<string, vector<string>> pre;// first是起点到second点的距离，second是顶点的名字
typedef pair<int, string> Pair; 
// 使用优先级队列，因为pair有比较运算，所以可直接传入
priority_queue<Pair, vector<Pair>, greater<Pair>> Q; int N, K;
string st, ed = "ROM";void Dijsktra(string s){cost[s] = 0;Q.push({cost[s].cost, s}); // push入起点while(!Q.empty()){Pair p = Q.top();Q.pop();string u = p.second;if(cost[u].cost < p.first) continue;for(Node next: G[u]){string v = next.name;int uv_cost = next.cost;if(cost[u].cost + uv_cost  < cost[v].cost){cost[v].cost = cost[u].cost + uv_cost;Q.push({cost[v].cost ,v}); // push入更短的Pairpre[v].clear();pre[v].push_back(u);} elseif(cost[u].cost + uv_cost == cost[v].cost){pre[v].push_back(u);}}}}vector<string> path, tempPath;
int routes = 0; // 相等cost的路径数量
int maxSumHappyness = -1; // 最大快乐值;
double maxAvgHappyness = -1; // 平均快乐值
void DFS(string v){if(v == st){routes++;tempPath.push_back(st);int sumhappyness = 0;double avghappyness = 0.0;for(string id: tempPath){sumhappyness += V[id];} avghappyness = sumhappyness / (tempPath.size() - 1);if(sumhappyness > maxSumHappyness){maxSumHappyness = sumhappyness;maxAvgHappyness = avghappyness;path = tempPath;}elseif(sumhappyness == maxSumHappyness){if(avghappyness > maxAvgHappyness){maxAvgHappyness = avghappyness;path = tempPath;  }}tempPath.pop_back();return;}tempPath.push_back(v);for(string u: pre[v]){DFS(u);}tempPath.pop_back();
}int main(){cin >> N >> K >> st;for(int i = 0;i < N-1;++i){ // 不输入起点的开心值，所以要N-1，并且给起点得到开心值初始化为0（被坑了）string city; int happy;cin >> city >> happy;V[city] = happy;}V[st] = 0;for(int i = 0;i < K;++i){string city1, city2; int cost;cin >> city1 >> city2 >> cost;G[city1].push_back({city2, cost});G[city2].push_back({city1, cost});}Dijsktra(st);DFS(ed);printf("%d %d %d %.0f\n",routes, cost[ed].cost, maxSumHappyness, maxAvgHappyness);for(int i = path.size() - 1;i >= 0;--i){cout << path[i];if(i != 0) cout << "->";else cout << "\n";}return 0;
}

    与本文相关的文章

    发布评论

    评论列表 (0)

    1. 暂无评论