小doge的快乐阳光跑

阳光跑"/>

小doge的快乐阳光跑

题目链接：小doge的快乐阳光跑

我们可以想一下，如果我们最开始肯定是从两个人的起点的其中一个作为起点，而且我们每次肯定是走最短路到达下一个任务点。

所以我们要预处理出所有任务点的最短路，然后每次跑的时候，我们可以想到，走最短路去做的任务有两个，到底是去哪一个任务点呢？

于是我们可以想到dp，dp[i][j][0/1] 代表当前在a的第i个任务点，和b的第j个任务点，并且最后停在了a的任务点，或者b的任务点所需的最短路。

然后dp一下即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int n,m,a[N],b[N],d[N][N],na,nb,dp[N][N][2];
int head[N],nex[N*20],to[N*20],w[N*20],tot;
inline void add(int a,int b,int c){to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
void dijkstra(int s){priority_queue<pair<int,int> > q;	q.push({0,s});	int vis[N]={0};d[s][s]=0;while(q.size()){int u=q.top().second;	q.pop();if(vis[u])	continue;	vis[u]=1;for(int i=head[u];i;i=nex[i]){if(d[s][to[i]]>d[s][u]+w[i]){d[s][to[i]]=d[s][u]+w[i];if(!vis[to[i]])	q.push({-d[s][to[i]],to[i]});}}}
}
signed main(){scanf("%lld %lld",&n,&m);while(m--){int a,b,c;	scanf("%lld %lld %lld",&a,&b,&c);	add(a,b,c);	add(b,a,c);}scanf("%lld",&na);for(int i=1;i<=na;i++)	scanf("%lld",&a[i]);scanf("%lld",&nb);for(int i=1;i<=nb;i++)	scanf("%lld",&b[i]);memset(d,0x3f,sizeof d);for(int i=1;i<=na;i++){if(!d[a[i]][a[i]])	continue;	dijkstra(a[i]);}for(int i=1;i<=nb;i++){if(!d[b[i]][b[i]])	continue;	dijkstra(b[i]);}memset(dp,0x3f,sizeof dp);for(int i=0;i<=n;i++)	d[0][i]=0;	dp[0][0][0]=dp[0][0][1]=0;for(int i=0;i<=na;i++){for(int j=0;j<=nb;j++){if(i){dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+d[a[i-1]][a[i]]);dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+d[b[j]][a[i]]);}if(j){dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+d[a[i]][b[j]]);dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+d[b[j-1]][b[j]]);}			}}printf("%lld\n",min(dp[na][nb][0],dp[na][nb][1]));return 0;
}