【SCAU18新生赛 论剑】 18362 寻找Megumi 多源最短路

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