PAT (Advanced Level) 1003. Emergency (25)

时间:2024-10-07 13:33:38

最短路+dfs

先找出可能在最短路上的边,这些边会构成一个DAG,然后在这个DAG上dfs一次就可以得到两个答案了。

也可以对DAG进行拓扑排序,然后DP求解。

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std; const int INF=0x7FFFFFFF;
const int maxn=;
int n,m,C1,C2,tot,ans1,ans2;
int val[maxn];
struct Edge
{
int u,v,L;
}e[];
int f[];
vector<int>g[maxn];
int dis[][maxn];
int h[maxn]; void init()
{
tot=;
for(int i=;i<=;i++) g[i].clear();
memset(h,,sizeof h);
} void add(int a,int b,int c)
{
e[tot].u=a,e[tot].v=b,e[tot].L=c;
g[a].push_back(tot);
tot++;
} void read()
{
scanf("%d%d%d%d",&n,&m,&C1,&C2);
for(int i=;i<n;i++) scanf("%d",&val[i]);
for(int i=;i<=m;i++)
{
int u,v,L; scanf("%d%d%d",&u,&v,&L);
add(u,v,L);
add(v,u,L);
}
} void SPFA(int f,int st)
{
for(int i=;i<=;i++) dis[f][i]=INF;
dis[f][st]=;
int flag[maxn]; memset(flag,,sizeof flag);
queue<int>Q; Q.push(st); flag[st]=;
while(!Q.empty())
{
int head= Q.front(); Q.pop(); flag[head]=;
for(int i=;i<g[head].size();i++)
{
int id=g[head][i];
if(dis[f][head]+e[id].L<dis[f][e[id].v])
{
dis[f][e[id].v]=dis[f][head]+e[id].L;
if(flag[e[id].v]==)
{
Q.push(e[id].v);
flag[e[id].v]=;
}
}
}
}
} void dfs(int x,int v)
{
if(x==C2)
{
ans1++; ans2=max(ans2,v);
return ;
} for(int i=;i<g[x].size();i++)
{
int id=g[x][i];
if(f[id]==) continue;
dfs(e[id].v,v+val[e[id].v]);
}
} void work()
{
int len=dis[][C2]; for(int i=;i<tot;i++)
if(dis[][e[i].u]+e[i].L+dis[][e[i].v]==len)
f[i]=; ans1=; dfs(C1,val[C1]);
printf("%d %d\n",ans1,ans2);
} int main()
{
init();
read();
SPFA(,C1);
SPFA(,C2);
work();
return ;
}