L3011直捣黄龙(PTA题解)xiaodangao

题目链接：L3-011 直捣黄龙
思路：提供两种思路，一种dfs嗯搜，一种迪杰斯特拉，因为数据量小，随便过，就是麻烦
$Code:$

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 400+10,inf = 0x3f3f3f3f;
int n,k;
string s,t,a[N];
map<string,int>S;
vector<int>G[N],val[N];
int pr[N];
bool st[N];int dis[N],d[N],cnt[N],f[N];
int head[N];
int ans[N],tot = 0;
void dij(int t){
    memset(dis,0x3f,sizeof dis);
    dis[0] = 0;//d[0] = pr[0];
    f[0] = 1;
    rep(i,1,n){
        int mx = inf,id = -1;
        rep(j,0,n-1){
            if(st[j])continue;
            if(dis[j]<mx){mx = dis[j];id = j;}
        }
        st[id] = true;
        int sz = (int)G[id].size();
        rep(j,0,sz-1){
            int p = G[id][j],q = val[id][j];
            if(dis[p] == dis[id] + q){
                if(cnt[p] < cnt[id] + 1){
                    cnt[p] = cnt[id] + 1;
                    d[p] = d[id] + pr[p];
                    head[p] = id;
                }
                else if(cnt[p] == cnt[id] + 1){
                    if(d[p] < d[id] + pr[p]){head[p] = id; }
                    d[p] = max(d[p] , d[id] + pr[p]);
                }
                f[p]+=f[id];
            }
            else if(dis[p] > dis[id] + q){
                head[p] = id;
                dis[p] = dis[id] + q;
                f[p] = f[id];
                cnt[p] = cnt[id] + 1;
                d[p] = d[id] + pr[p];
            }
        }
    }
    int now = t;
    while(now!=0){ans[++tot] = now;now = head[now]; }
    ans[++tot] = 0;
    bep(i,tot,1){
        cout<<a[ans[i]];if(i!=1)cout<<"->";
    }
    cout<<endl;
    cout<<f[t]<<' '<<dis[t]<<' '<<d[t]<<endl;
    //write(d[t]);pc('\n');write(f[t]);pc('\n');write(dis[t]);//pc('\n');write(cnt[t]);
}
int tt ,high,mx = -1,mi = inf,c = 0,mx2 = -1;
vector<int>ANS;
void dfs(int id,int sum,int sum2){
    int sz = (int)G[id].size();
    if(id == tt){
        if(sum > mi)return ;
        if(sum == mi){
            c++;
            if(mx > high)return;
            else if(mx == high){
                if(mx2 >= sum2)return ;
            }
            mx = high;
            mx2 = sum2;
            ANS.clear();
            rep(i,1,high)ANS.pb(ans[i]);
        }
        else {
            c=1;
            mx = high;mx2 = sum2;mi = sum;ANS.clear();rep(i,1,high)ANS.pb(ans[i]);
        }
        return ;
    }
    st[id] = true;
    rep(i,0,sz-1){
        int p = G[id][i];
        int q = val[id][i];
        if(st[p])continue;
        ans[++high] = p;
        dfs(p,sum + q,sum2 + pr[p]);
        --high;
    }
    st[id] = false;
}
void solve(){
    cin>>n>>k>>s>>t;
    rep(i,1,n-1){
        string u;int v;
        cin>>u>>v;
        a[i] = u;
        S[u] = i;pr[i] = v;d[i] = v;cnt[i] = 1;
    }a[0] = s;
    S[s] = 0;
    rep(i,1,k){
        string u,v;int d;
        cin>>u>>v>>d;
        int idx = S[u],idy = S[v];
        G[idx].pb(idy);G[idy].pb(idx);
        val[idx].pb(d);val[idy].pb(d);
    }
    tt = S[t];
    dfs(0,0,0);
    cout<<s;
    rep(i,0,(int)ANS.size()-1)cout<<"->"<<a[ANS[i]];
    cout<<endl;
    cout<<c<<' '<<mi<<' '<<mx2<<endl;
}
signed main(){
    //puts("0");
    solve();
    return 0;
}

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章