The title is as above.

Violent milling, n^2 million!!

As a puzzle, it does have a little water (if it's an animal solution)

It is to find the minimum value of the shortest path between two points.

Originally a very deep question, to run twice the shortest path, and then dye ah, and then expand what, but! One of the fairies (not bk201) was violent.

Solution:

Consider an algorithm called dijkstra (there must be no spfa here). How does it run?

Simply, greedy to find the current shortest path, and then use the next node to expand the next node.

However, goose, if this process runs the whole picture, it will explode into M78 nebula!!!

However, because of the wonderful greedy correctness of dijkstra, the first node we extend to is the current minimum, so we

Back! Out!

Grandpa, I won't run away!

This wave of operation is really very immortal!!!

Through this lovely return, we save a lot of time and space, there are many points can not run!

(The essence is an n^2 violence.)

The magic is that the complexity of this dij should be inversely related to the number of points, marker points. If the value of n-k is smaller, the speed of dij will be faster. Of course, if n-k=0, then the dij is basically linear, no, O (1), and even can be replaced by the minimum value of side ratio scanned at one time.

So it is a pseudo n^2 algorithm.

(Then he learned a new dijk method with the zrx guys.)

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+10;
ll n,m,k;
struct edge
{
    ll to,next,dis;
}e[maxn];
ll cnt,head[maxn];
inline void addedge(ll from,ll to,ll dis)
{
    e[++cnt].next=head[from];
    e[cnt].to=to;
    e[cnt].dis=dis;
    head[from]=cnt;
}
struct node//Manual Reactor Optimization
{
    ll x;
    ll v;
    bool operator <(const node &an)const
    {
        return v>an.v;
    }
};
ll dis[maxn];
bitset < maxn > vis,fl;
ll dijkstra(int s)
{
    priority_queue < node > q;
    vis.reset();
    memset(dis,0x3f,sizeof(dis));
    q.push((node){s,0});
    dis[s]=0;
    while(!q.empty())
    {
        node s1=q.top();
        q.pop();
        ll u=s1.x;
        if(fl[u]!=0&&u!=s)//The first non-starting marker
        return dis[u];//Direct return to minimum distance
        if(vis[u]==0)//Continue dij
        {
            vis[u]=1;
            for(ll i=head[u];i;i=e[i].next)
            {
                int v=e[i].to;
                if(dis[v]>dis[u]+e[i].dis)
                {
                    dis[v]=dis[u]+e[i].dis;
                    q.push((node){v,dis[v]});
                }
            }
        }
    }
    return 0x3f3f3f3f3f3f3f3f;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cnt=0;
        memset(head,0,sizeof(head));
        fl.reset();
        scanf("%lld%lld%lld",&n,&m,&k);
        for(ll i=1;i<=m;i++)
        {
            ll x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            addedge(x,y,z);
        }
        for(ll i=1;i<=k;i++)
        {
            ll x;
            scanf("%lld",&x);
            fl[x]=1;
        }
        ll ans=0x3f3f3f3f3f3f3f3f;
        for(ll i=1;i<=n;i++)
        {
            if(fl[i]!=0)//Every marker runs once.
            ans=min(dijkstra(i),ans);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

There are surprises downward.

Admire the man below and have time to go to his blog.

https://www.cnblogs.com/2529102757ab/

(End)