1.练习项目  ：

问题描述

”大鱼吃小鱼，小鱼吃虾米。“

但是，小鱼也有变成大鱼的梦想！

小鱼住在一个有 n 个区域的海底世界，区域编号从 1 到 n，海底世界中有 m 条单向通道，每条通道连接了其中两个区域。

区域 1 有海底世界中唯一的虾米群。

区域 2 到 n 中，有 k 个区域可以作为出生点，即小鱼可以任意选择其中一个区域作为起点，它将从该起点出发，游到区域 1，从而吃到虾米群，变成大鱼。

现在小鱼希望选择某个出生点，使得它从该出生点出发，到吃到虾米群的总距离最短。请你帮帮它。

输入格式

第一行，一个整数 t，表示测试案例的个数。（1≤t≤10）

对于每个测试案例：

• 第一行，三个整数 n,m,k，表示海底世界的区域个数、单向通道条数、出生点个数。（2≤n≤104，1≤m≤104，1≤k≤n−1）​

• 第二行，k 个整数，表示出生点的编号 vi​。（2≤vi≤n）

• 接下来 m 行，每行三个整数 a,b,c，表示存在一条从区域 a 到区域 b 的长度为 c 的单向通道。（1≤a,b≤n，1≤c≤105）

输出格式

共 t 行，每行一个整数，表示吃到虾米的最短距离，若无论取哪个出生点，都无法吃到虾米，则为 −1。

2.选择课程

在蓝桥云课中选择题库，选择题号19849并开始练习。

3.开始练习

（1）虚拟源点     ：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e4+10;
const ll inf = 2e18;

struct Edge{
    ll x,w;
    bool operator <(const Edge &u)const{
        return (w == u.w ? x < u.x:w > u.w);
    }
};

vector<Edge>g[N];
ll d[N],n,m,k;

void dijkstra()
{
    //初始化
    for(int i=0;i<=n;i++)d[i]=inf;
    //变量
    priority_queue<Edge>pq;
    bitset<N>vis;
    pq.push({0,d[0]=0});
    //循环pq
    while(pq.size()){
        //拓展（松弛）
        int x=pq.top().x;pq.pop();
        if(vis[x])continue;
        vis[x]=true;
        for(const auto&t:g[x]){
            int y=t.x;
            int w=t.w;
            if(d[x]+w<d[y]){
                //说明st > ... > y这条边可以被st > ... > x > y松弛掉
                pq.push({y,d[y]=d[x]+w});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        cin>>n>>m>>k;
        for(int i=0;i<=n;i++)g[i].clear();
        for(int i=1;i<=k;i++){
            int x;cin>>x;
            g[0].push_back({x,0});
        }
        for(int i=1;i<=m;i++){
            ll x,y,w;cin>>x>>y>>w;
            g[x].push_back({y,w});
        }
        dijkstra();
        if(d[1]>=inf)cout<<-1<<'\n';
        else cout<<d[1]<<'\n';
    }
    return 0;
}

（2）反图：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e4+10;
const ll inf = 2e18;

struct Edge{
    ll x,w;
    bool operator <(const Edge &u)const{
        return (w == u.w ? x < u.x:w > u.w);
    }
};

vector<Edge>g[N];
ll d[N],n,m,k;

void dijkstra()
{
    //初始化
    for(int i=1;i<=n;i++)d[i]=inf;
    //变量
    priority_queue<Edge>pq;
    bitset<N>vis;
    pq.push({1,d[1]=0});
    //循环pq
    while(pq.size()){
        //拓展（松弛）
        int x=pq.top().x;pq.pop();
        if(vis[x])continue;
        vis[x]=true;
        for(const auto&t:g[x]){
            int y=t.x;
            int w=t.w;
            if(d[x]+w<d[y]){
                //说明st > ... > y这条边可以被st > ... > x > y松弛掉
                pq.push({y,d[y]=d[x]+w});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++)g[i].clear();
        vector<int>v;
        for(int i=1;i<=k;i++){
            int x;cin>>x;
            v.push_back(x);
        }
        for(int i=1;i<=m;i++){
            ll x,y,w;cin>>x>>y>>w;
            g[y].push_back({x,w});
        }
        dijkstra();
        ll ans=inf;
        for(const auto&x:v)ans=min(ans,d[x]);
        if(ans>=inf)cout<<-1<<'\n';
        else cout<<ans<<'\n';
    }
    return 0;
}

（2）检验结果

对此代码进行检验，检验后无报错，提交此代码，判题结果为正确100分。

（3）练习心得：注意每段代码末尾的分号是否存在   ，如不存在则需即使补充；输入法    是否切换 为英语模式；语法是否错误。