Description
女神Megumi将要在scau开签名会。为了拿亲笔签名，众人纷纷前往。但是伦也童鞋决定要自己组装一个漂亮的签名本，
这个签名本需要到很多个地方收集材料。但是他是个路痴，他想知道如何用最快的形式获取这些材料然后去寻找Megumi。
已知scau是一个n个节点m条边的图，伦也需要到k个地方收集材料，a0,a1,…,ak，由于伦也智商有限，这些材料必须按
顺序收集。伦也从点1出发，Megumi在点n。请问他需要至少用多少时间到达？
输入格式
第一行一个整数T，代表有T（T < 10）个test case。
对于每个case，第一行两个数n,m，表示有n个节点，m条边后面是m行，每行两个整数a,b表示点a和点b之间有路，可以
从a走到b，也可以从b走到a。后面一行是一个整数k，表示需要到k个点收集材料。后面一行是k个整数，表示中途需要搜
集材料的位置，保证不会存在起点和终点。（m <= n <= 1000, k < n - 1）
输入保证路径必定存在。
输出格式
对每个test case输出一行，从点1收集完所有材料到达点n所需要的最小时间。
输入样例
1
3 3
1 2
2 3
1 3
1
2
输出样例
2
| 题意：上面够简洁了 |
算法思路（多源最短路）：
1.首先理解题目意思，其实还是一个从1->n的问题，只是中间要途径k个点。这些点还得按顺序来，因为每次我贪心的从a[i-1]走到a[i]的最短路是肯定最优的，因为没有后效性。所以这个问题就变成了一个多源最短路的问题，是一个每次起点为a[i-1]，到a[i]的多源最短路问题。
2.但是多源最短路的话，最直接的当然是floyd，不过这里1000个数据应该会TL飞，所以考虑堆优化的Dijkstra最短路，每次枚举起点s（s从1->a[1]->a[2]…->a[k]），然后累加跑出来d[t]（到终点的最短路）即可。
AC代码：
我要评论#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn = 1e6+5;
const ll inf=0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') ch = getchar();while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };
const int V = 3e3, E=3e3;
ll d[V],cost[E];
ll n,m;
ll head[V],pnt[E],nxt[E],e=0;
ll vis[V];
ll a[V];
void addedge(ll u,ll v,ll c)
{
pnt[e]=v; //当前以u为顶点，c为边长的，到v的一条边
cost[e]=c; //存入当前边权值
nxt[e]=head[u]; //下一个其实是前一个
head[u]=e++; //当前边编号
}
inline void Dijkstra(ll s)
{
mem(d,inf); mem(vis,0);
priority_queue<PII, vector<PII>, greater<PII> > q;
d[s] = 0;
q.push(mp(0LL,s));
while(!q.empty())
{
ll x = q.top().se; q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i=head[x];i!=-1;i = nxt[i])
{
ll v = pnt[i];
if(d[v]>d[x]+cost[i]&&!vis[v])
{
d[v] = d[x] + cost[i];
q.push(mp(d[v], v));
}
}
}
//return d[n]==inf?-1:d[n];
}
int main()
{
int kase;
cin>>kase;
while(kase--)
{
e = 0; mem(head,-1);
mem(d,inf); mem(vis,0);
n = read(), m = read();
rep(i,1,m)
{
ll x = read(), y = read();
addedge(x,y,1);
addedge(y,x,1);
}
ll pos = 0;
a[pos++] = 1; //第一位放1
ll k = read(); //读入k个数
rep(i,1,k) a[pos++] = read();
a[pos] = n; //最后一位放n
ll sum = 0;
rep(i,1,pos) //然后枚举起点为a[i-1]，终点为a[i]，跑最短路取d[t]即可。
{
ll s = a[i-1], t = a[i];
Dijkstra(s);
ll ans = d[t];
sum += ans;
}
cout<<sum<<'\n';
}
return 0;
}
本文地址：https://blog.csdn.net/qq_45492531/article/details/107333932
如对本文有疑问， 点击进行留言回复！！
offset、client、scroll (width,height、left,top、X,Y)
网友评论