I'm late for school

Unit shortest path problem

Topic link

The following is the explanation of this topic written by a blogger who happened to see it , Personally, I think it's very good ！！
A blogger explained in depth

This is the same blog that the blogger spent a long time writing , It can be said that great efforts have been injected , I have written down my understanding of the algorithm
Have a thorough understanding of dijkstra+ Heap optimization code idea

Title Description

Niuniu gets up in the morning and has a look , I slept , Get up and get ready to go to school , There are only two ways for him to go to school , Take the bus and walk , Niuniu goes to school in a straight line , There are a total of on this line n A station , The distance between the stations is equal , There is only one kind of bus at each station a_i, Each bus stops only at the corresponding bus stop , The speed of each bus is also different , The first i It takes time for a bus to pass a stop t_i, And the bus runs in one direction , Only from left to right , You can walk at will , However, the time it takes Niuniu to walk one stop by himself is T, It happens that Niuniu's home and school are at a certain site , Respectively s and t, How much time does it take to get to school ？

Topic analysis ： This is a very good topic , I think the main test sites are under construction , A very ingenious method of drawing , It was meant to clarify my thinking , But I happened to see an explanation , It's a great sight , So learn from bloggers' blogs , The blogger spoke very thoroughly , It can be seen that the blogger is writing a blog carefully , A thoughtful blog is worth caring for .

Let's talk about the method of drawing construction , We just need to build a road between two adjacent points , Others can be transferred

Where every bus can park is one-way , It can be represented as a directed edge in the graph . Be careful. , The directed edge we want to store is not the directed edge from each station to all the stops behind it , It is the directed edge of the adjacent parking station , such as 1 2 2 1 2 1 1 2 1, For the first position 1 For cars , We just need to match it to the fourth position 1 The car builds a one-way edge , There is no need to connect with the sixth position 1 Car construction has a directed edge , Because as long as the directed edges of adjacent parking stations are constructed , It can be built naturally through the transfer of state , This is it. Dijkstra What the algorithm does , So you don't have to do it .

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int pre[maxn], last[maxn], a[maxn], dis[maxn];
const int inf = 0x3f3f3f3f;
#define pii pair<int, int>
int n, m, s, t, T;
vector<pii> g[maxn];
void dijkstra()
{
    
    memset(dis, inf, sizeof(dis));
    dis[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push(make_pair(0, s));// The first position in the queue stores the distance from the source point to this point , The second position records the information of this point 
    while (!q.empty())
    {
    
        pii p = q.top();
        q.pop();
        int u = p.second;
        if (dis[u] < p.first)// If the distance is less than p.first, Then there is no need to update 
            continue;
        for (int i = 0; i < g[u].size(); ++i)// Traverse the adjacency point of the change point 
        {
    
            int v = g[u][i].second, w = g[u][i].first;
            if (dis[v] > dis[u] + w)
            {
    
                dis[v] = dis[u] + w;
                q.push(make_pair(dis[v], v));
            }
        }
    }
}
int main()
{
    
    scanf("%d%d%d%d%d", &n, &m, &s, &t, &T);
    for (int i = 1; i <= m; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)// Drawing 
    {
    
        int x;
        scanf("%d", &x);
        if (last[x])// If this point is not the starting point of the bus , It's a stop somewhere in the middle , Then save the bus information 
            g[last[x]].push_back(make_pair(a[x], i));
        last[x] = i;// Record the position of adjacent points , Points between nonadjacency can be reached by transfer 
        // Walk to create two-way edges 
        g[i].push_back(make_pair(T, i - 1));
        g[i - 1].push_back(make_pair(T, i));
    }
    dijkstra();
    printf("%d\n", dis[t]);
}

Self discipline is an attitude towards life , It is a kind of spirit of being a master only after suffering , It is a long-term investment of one person , It is also a kind of , Exchange endless loneliness for the envy of others and the glory of oneself

A good friend of mine , A few days ago, Baoyan Tsinghua succeeded , My friend , I have been excellent since primary school , Always top a few in age , I have always envied his amazing report card , But with a long time of contact , I also learned that hard work is behind the amazing , And he is extremely disciplined

He's sunny , Very energetic ,, Also very handsome , Is a forever white shirt boy , It is also the first love in the hearts of countless girls , Ha ha ha

Here it is , Bless him , The future is bright ！！ To rush ~

My favorite this year is it