寒假刷题第六天

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;
}