题目链接: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;
}