寒假刷题第六天

PTA甲级

1030 Travel Plan

迪杰斯特拉

#include<iostream>
#include<vector>
#include<cstring>using namespace std;const int N = 510 , INF = 0x3f3f3f3f3f;
int n , m , s , d;
int g[N][N] , cost[N][N] , dist[N] , min_cost[N];
bool st[N];
int path[N];int main()
{memset(g , 0x3f , sizeof g) , memset(cost , 0x3f , sizeof cost);memset(dist , 0x3f , sizeof dist) , memset(min_cost , 0x3f , sizeof min_cost);memset(st , 0 , sizeof st);cin >> n >> m >> s >> d;while(m --){int a , b , c , e;cin >> a >> b >> c >> e;g[a][b] = g[b][a] = c;cost[a][b] = cost[b][a] = e;}dist[s] = 0;min_cost[s] = 0;for(int i = 0;i < n;i ++){int t = -1;for(int j = 0;j < n;j ++)if(!st[j] && (t == -1 || dist[t] > dist[j]))t = j;st[t] = true;for(int j = 0;j < n;j ++){if(dist[j] > dist[t] + g[t][j]) {dist[j] = dist[t] + g[t][j];path[j] = t;min_cost[j] = min_cost[t] + cost[t][j];}else if(dist[j] == dist[t] + g[t][j]){if(min_cost[j] > min_cost[t] + cost[t][j]){min_cost[j] = min_cost[t] + cost[t][j];path[j] = t;}}}}vector<int>res;for(int i = d;i != s;i = path[i]) res.push_back(i);res.push_back(s);for(int i = res.size() - 1;i >= 0;i --)cout << res[i] << " ";cout << dist[d] << " " << min_cost[d];return 0;
}

1034 Head of a Gang

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<set>using namespace std;typedef pair<string , int> PSI;
int n , k;
unordered_map<string , vector<PSI>>g;
unordered_set<string>se;
unordered_map<string , bool>st;
unordered_map<string , int>total;int dfs(string i , vector<string>&v)
{st[i] = true;v.push_back(i);int sum = 0;for(auto j : g[i]){string x = j.first;int y = j.second;sum += y;if(!st[x]) sum += dfs(x , v);}return sum;
}int main()
{cin >> n >> k;while(n --){string a , b;int x;cin >> a >> b >> x;g[a].push_back({b , x});g[b].push_back({a , x});se.insert(a) , se.insert(b);total[a] += x , total[b] += x;}vector<PSI>res;for(auto i : g){vector<string>v;int sum = dfs(i.first , v) / 2;if(v.size() <= 2) continue;if(sum <= k) continue;string boss = v[0];for(auto j : v)if(total[boss] < total[j]) boss = j;res.push_back({boss , v.size()});}cout << res.size() << endl;sort(res.begin() , res.end());for(auto i : res)cout << i.first << " " << i.second << endl;return 0;
}