欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-09 12:59:03
Description女神Megumi将要在scau开签名会。为了拿亲笔签名,众人纷纷前往。但是伦也童鞋决定要自己组装一个漂亮的签名本,这个签名本需要到很多个地方收集材料。但是他是个路痴,他想知道如何用最快的形式获取这些材料然后去寻找Megumi。已知scau是一个n个节点m条边的图,伦也需要到k个地方收集材料,a0,a1,…,ak,由于伦也智商有限,这些材料必须按顺序收集。伦也从点1出发,Megumi在点n。请问他需要至少用多少时间到达?输入格式第一行一个整数T,代表有T(T < 10)...

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