20220721 beaten content

Not today upc, Because I want to concentrate on learning the knowledge of graph theory , Indeed and dp,dfs,bfs It's really difficult to build a map by combining them , Really abused

1135. Happy New Year

There are... In Chongqing  nn  A station ,mm  strip   two-way   The highway connects some of these stations .

Every two stations can be connected by one highway at most , From any station, you can go through one or more roads to other stations , But different paths may take different time .

The time spent on a path is equal to the sum of the time required for all roads on the path .

Jiajia's home is at the station  11, He has five relatives , Live in the station  a,b,c,d,ea,b,c,d,e.

Celebrate the new year , He needs to start from his home , Visit every relative （ Any order ）, Send them holiday wishes .

How to go , It takes the least time ？

Input format

first line ： Contains two integers  n,mn,m, Indicates the number of stations and roads respectively .

The second line ： Contains five integers  a,b,c,d,ea,b,c,d,e, It indicates the station number of five relatives .

following  mm  That's ok , Three integers per row  x,y,tx,y,t, Indicates the number and time of two stations connected by the highway .

Output format

Output only one line , Contains an integer  TT, Represents the minimum total time .

Data range

1≤n≤500001≤n≤50000,
1≤m≤1051≤m≤105,
1<a,b,c,d,e≤n1<a,b,c,d,e≤n,
1≤x,y≤n1≤x,y≤n,
1≤t≤1001≤t≤100

sample input ：

6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7

sample output ：

21

          The difference between this topic and the shortest path problem usually done is that it involves the problem of Full Permutation , That is, from the beginning , Go first 1 To 5 Which of these five points , Go to the next point , He has different sorting methods , therefore , We have to think about dfs This solution .

        The first thing we need to change is that we usually use dist It is one dimension to store distance , But this time we will open a two-dimensional array ,dist[i][j] Representative to i From... To j The shortest path of the point . So we need to do five shortest path algorithm .

        Then consider the choice of Algorithm , The first thing to consider is spfa and dijkstra Heap optimization based on FPGA ,1≤n≤50000
1≤m≤1e5, There is a lot of data to say and give . The first consideration is to use dijkstra To write! .

First write dfs Partial content

void dfs(int start, int u, int distance) {

        if (u > 5) return distance; // This is the deadline

        int res = INF;

        for (int i = 1; i <= 5; i++) {

                if (!st[j]) {

                        int next = source[i]; // Let him be equal to i The number of

                        st[i] = true;// Was chosen

                        res = min(res, dfs(u + 1, next, distance + dist[start][next]); // from start To next Distance of

                        st[i] = false;// Go back to

                }

        }

        return res;

 }

And then there's the code ：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int,int> PII;

const int N = 50010, M = 2e5+ 10, INF = 0x3f3f3f3f;
int e[M], ne[M], w[M], h[N], idx;
int dist[6][N];
bool st[N];
int source[N];
int n, m;

void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

void dijkstra(int start, int dist[]) {
    memset(dist, 0x3f, N * 4);
    memset(st, false, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII> > heap;
    dist[start] = 0;
    heap.push({0, start});
    
    while (heap.size()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int dfs(int u, int start, int distance) {
    if (u >= 6) return distance;
    int res = INF;
    
    for (int i = 1; i <= 5; i ++) {
        if (!st[i]) {
            int next = source[i];
            st[i] = true;
            res = min(res, dfs(u + 1, i, distance + dist[start][next]));
            st[i] =false;
        }
    }
    
    return res;
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    source[0] = 1;
    for (int i = 1; i <= 5; i++) {
        cin >> source[i];
    }
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    
    for (int i = 0; i <= 5; i++) dijkstra(source[i], dist[i]);
    memset(st, 0, sizeof st);
    printf("%d\n", dfs(1, 0, 0));
    return 0;
}

It's too hard , It really tests code strength .

340. Communication lines

In the suburbs  NN  A communication base station ,PP  strip   two-way   cable , The first  ii  A cable connects the base station  AiAi  and  BiBi.

Specially ,11  Base station No. 1 is the main station of the communication company ,NN  Base station is located in a farm .

Now? , The farmer wants to upgrade the communication line , Among them, upgrade the second  ii  This cable costs  LiLi.

The telephone company is holding a discount .

The farmer can designate a route from  11  Base station to  NN  The path of base station No , And specify no more than... On the path  KK  Cables , Free upgrade service provided by the telephone company .

Farmers only need to pay for the remaining cables on the path , The cost of upgrading the most expensive cable .

Ask at least how much money can be used to complete the upgrade .

Input format

The first  11  That's ok ： Three integers  N,P,KN,P,K.

The first  2..P+12..P+1  That's ok ： The first  i+1i+1  The row contains three integers  Ai,Bi,LiAi,Bi,Li.

Output format

Contains an integer indicating the least cost .

if  11  Base station No. 1 and  NN  There is no path between base stations , The output  −1−1.

Data range

0≤K<N≤10000≤K<N≤1000,
1≤P≤100001≤P≤10000,
1≤Li≤10000001≤Li≤1000000

sample input ：

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

sample output ：

4

  The big one is coming ！

ok , I admit I haven't figured out how to write two points , Then I'll stick the code of two points first .

Excerpt some ideas of others ：

    The title of this question means , Given an undirected graph , Find a slave node 1 To the node N The route of the , Remove the front of the route k Big value , Compare the remaining maximum values , The goal is to find the smallest value ; It's a bit awkward , In fact, this problem is to find a route , Make this route the first k+1 A large value is the smallest .

        Find the maximum and the minimum , The general method is to use dichotomy , Give a value bound, Judge the middle ratio of the route bound Whether the large value is less than or equal to k individual , If so , explain bound It's legal. , Can increase bound; If it is greater than k individual , Note No k+1 Large value ratio bound Big , that bound It needs to be updated in the big direction , At the end of an iteration, find the boundary polar line , That is the final result , See code .

Woo woo No

#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;

const int N = 1010, M = 20010;

int n, m, k;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
deque<int> q;
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool check(int bound)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    q.push_back(1);
    dist[1] = 0;

    while (q.size())
    {
        int t = q.front();
        q.pop_front();

        if (st[t]) continue;
        st[t] = true;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i], x = w[i] > bound;
            if (dist[j] > dist[t] + x)
            {
                dist[j] = dist[t] + x;
                if (!x) q.push_front(j);
                else q.push_back(j);
            }
        }
    }

    return dist[n] <= k;
}

int main()
{
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    int l = 0, r = 1e6 + 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    if (r == 1e6 + 1) cout << -1 << endl;
    else cout << r << endl;

    return 0;
}

a farmer John There are many pastoral areas on our farm , Some paths connect some specific pastoral areas .

A connected pastoral area is called a pasture .

But for now , You can see that at least two pastoral areas are not connected .

Now? ,John Want to add a path to the farm （ Be careful , Just one ）.

The diameter of a pasture is the distance between the two farthest pastures in the pasture （ All the distances mentioned in this question refer to the shortest distance ）.

Consider the following two pastures , Each pastoral area has its own coordinates ：

chart 1 Yes, there is 5 A pastoral area , For pastoral areas “*” Express , The path is represented by a straight line .

chart 1 The diameter of the pasture shown is about 12.07106, The two farthest pastoral areas are A and E, The shortest path between them is A-B-E.

chart 2 It's another ranch .

Both pastures are John On my farm .

John One pastoral area will be selected from each of the two pastures , Then connect them with a path , Make this new and larger pasture have the smallest diameter after connection .

Be careful , If two paths intersect halfway , We don't think they are connected .

Only two paths intersect in the same pastoral area , We think they are connected .

Now please program to find a path connecting two different pastures , So that when connected to this path , All pastures （ New and existing pastures ） The largest pasture in diameter should be as small as possible .

Output the minimum possible value of this diameter .

Input format

The first 1 That's ok ： An integer N, Indicates the number of pastoral areas ;

The first 2 To N+1 That's ok ： Two integers per line X,Y, Express N The coordinates of the pastoral area . The coordinates of each pastoral area are different .

The first N+2 Go to the first place 2*N+1 That's ok ： Each line includes N A digital ( 0 or 1 ) Represents a symmetric adjacency matrix .

for example , The matrices of the two pastures in the title description are described as follows ：

  A B C D E F G H 
A 0 1 0 0 0 0 0 0 
B 1 0 1 1 1 0 0 0 
C 0 1 0 0 1 0 0 0 
D 0 1 0 0 1 0 0 0 
E 0 1 1 1 0 0 0 0 
F 0 0 0 0 0 0 1 0 
G 0 0 0 0 0 1 0 1 
H 0 0 0 0 0 0 1 0

The input data includes at least two disconnected pastoral areas .

Output format

There is only one line , Include a real number , Means the answer you want .

The number retains six decimal places .

Data range

1≤N≤150
0≤X,Y≤1e5

sample input ：

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

sample output ：

22.071068

  The input of this topic is abstract enough ,

There are too many things , I can't finish writing , Have time to add