20220722 beaten record

I feel dizzy today , I feel like I haven't done anything ！

one day , Kiki wants to take a bus to visit one of her friends .

Because Kiki gets carsick very easily , So she wants to get to her friend's house as soon as possible .

Now let's give you a city traffic map , The above includes the specific distribution of the city's bus stops and bus lines .

Known cities contain  nn  A station （ Number 11~nn） as well as  mm  It's a bus line .

Every bus line is   One way , Start from one station and go straight to another station , There may be multiple bus lines between two stations .

Kiki's friends live in  ss  Near station No .

Kiki can choose to change to other buses at any station .

Please find Kiki and get to her friend's house （ A nearby bus stop ） The least time it takes .

Input format

Input contains multiple sets of test data .

The first row of each set of test data contains three integers  n,m,sn,m,s, Respectively represent the number of stations , The number of bus routes and the number of stations near friends' homes .

Next  mm  That's ok , Each line contains three integers  p,q,tp,q,t, Indicates that there is a line from the station  pp  Get to the station  qq, The time is  tt.

Next line , Contains an integer  ww, There are... Near Qiqi's house  ww  A station , She can be here  ww  Select one of the stations as the departure station .

Another line , contain  ww  It's an integer , It means... Near Qiqi's house  ww  Number of stations .

Output format

Output an integer for each test data as the result , Indicates the minimum time required .

If you can't reach a friend's station , The output -1.

Each result takes up one line .

Data range

n≤1000,m≤20000n≤1000,m≤20000,
1≤s≤n1≤s≤n,
0<w<n0<w<n,
0<t≤10000<t≤1000

sample input ：

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

sample output ：

1
-1

This topic is a reverse mapping process , Because if we add(a, b, c) On behalf of a towards b Create an edge , If so , We can't find the shortest way to a friend's bus station , We can only find the shortest path with our own home as the origin each time , But if the reverse is true , That is to say, take a friend's home as the starting point , Let friends find themselves , Reverse side building , Does this mean that you can only run once dijkstra I can solve the problem by pasting two kinds of codes , The first is to build a positive edge , It will time out. The second kind is ac 了

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

using namespace std;
const int N = 1010, M = 40010, INF = 0x3f3f3f3f;

typedef pair<int,int> PII;
int h[N], e[M], ne[M], w[M],  idx;
bool st[N];
int dist[N];
int n, m, S;

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) {
	memset(st, 0, sizeof st);
        memset(dist, 0x3f, sizeof dist);
        dist[start] = 0;
        priority_queue<PII, vector<PII>, greater<PII> > heap;
        heap.push({dist[start], 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; 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 main() {
    while (cin >> n >> m >> S) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
        }
        
        
        int s;
        cin >> s;
        int res = INF;
        while (s --) {
            int a;
            cin >> a;
            dijkstra(a);
            res = min(res, dist[S]);
        }
        if (res == 0x3f3f3f3f) puts("-1");
        else cout << res << endl;
    }    
}

  This is a ac Of

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

using namespace std;
const int N = 1010, M = 40010, INF = 0x3f3f3f3f;

typedef pair<int,int> PII;
int h[N], e[M], ne[M], w[M],  idx;
bool st[N];
int dist[N];
int n, m, S;

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

int main() {
    while (cin >> n >> m >> S) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            add(b, a, c);
        }
        
        memset(st, 0, sizeof st);
        memset(dist, 0x3f, sizeof dist);
        dist[S] = 0;
        priority_queue<PII, vector<PII>, greater<PII> > heap;
        heap.push({dist[S], S});
        
        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; 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 s;
        cin >> s;
        int res = INF;
        while (s --) {
            int a;
            cin >> a;
            res = min(res, dist[a]);
        }
        if (res == 0x3f3f3f3f) puts("-1");
        else cout << res << endl;
    }    
}

Write these first , I add

Here comes the follow-up , It also adds the idea of super source , You can connect yourself to this source , Add your starting point to the queue , Then put their dist Set to 0 Just fine , We only need to do the shortest path algorithm once , There is no need to add edges in reverse .

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

using namespace std;
const int N = 1010, M = 40010, INF = 0x3f3f3f3f;

typedef pair<int,int> PII;
int h[N], e[M], ne[M], w[M],  idx;
bool st[N];
int dist[N];
int n, m, S;
int q[N];

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

int main() {
    while (cin >> n >> m >> S) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
        }
        int tt = 0, hh = 0;
        memset(st, 0, sizeof st);
        memset(dist, 0x3f, sizeof dist);
        int s;
        cin >> s;
        int res = INF;
        while (s --) {
            int a;
            cin >> a;
            dist[a] = 0;
            st[a] = true;
            q[tt ++] = a;

        }

        while (hh != tt) {
            int u = q[hh ++];
            if (hh == N) hh = 0;
            st[u] = false;

            for (int i = h[u]; ~i; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[u] + w[i]) {
                    dist[j] = dist[u] + w[i];
                    if (!st[j]) {
                        q[tt ++] = j;
                        if (tt == N) tt = 0;
                        st[j] = true;
                    }
                }
            }
        }
        if (dist[S] == 0x3f3f3f3f) puts("-1");
        else printf("%d\n", dist[S]);
    }    

    return 0;
}

Continue to update ┗|｀O′|┛ Ow ~~

This is a way flyod The subject of , Anyway, it's an eye opener hahaha

1125. The journey of cattle

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≤1501≤N≤150,
0≤X,Y≤1050≤X,Y≤105

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

  First, let's introduce variables ：

typedef pair<double,double> PDD;

char map[N][N];  This is to store the original map
double g[N][N]; This one uses adjacency matrix to store distance
PDD store[N]; This is the first time to input coordinates and store coordinates
double max1[N]; This is the farthest distance from this point

The difficulty of the topic , How to add side

The first thing we consider is to use flyod Apply board , In this case, if for i and j Two points , If their distance is greater than what we set INF / 2 Does that mean there is no shortest path between them , Can be in i and j Create an edge between , So we just need to find the distance i The farthest point and distance j The farthest point , The value obtained is max1[i] + max1[j] + i and j Distance on the map , This is also the diameter we obtained ！

What we are looking for is the maximum and the minimum （ Really contradictory hhhh

Let's ask first ans2, Represents the maximum diameter without edge

Then we traverse all points , If the distance between two points is greater than INF / 2 Just go and ans Compare and take the largest ,

Last sum ans2 Take the smallest

Also note the initialization size ,double, Be confident and open wider

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
const int N = 200, M = N *N * 2;
const double INF = 1e20;
typedef pair<double,double> PDD;

char map[N][N];
double g[N][N];
PDD store[N];
double max1[N];

double get_dis(PDD a, PDD b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

int main() {
    int n, m;
    cin >> n;
    for (int i = 0; i < n; i++) {
        double x, y;
        cin >> x >> y;
        store[i] = {x, y};
    }
    
    for (int i = 0; i < n; i++) cin >> map[i];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) map[i][j] = 0;
            else if (map[i][j] == '1') {
                g[i][j] = get_dis(store[i], store[j]);
            } else {
                g[i][j] = INF;
            }
        }  
    }
    for (int k = 0; k < n; k++){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);        
            }
        }
    }
    double ans2 = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] < INF / 2) {
                max1[i] = max(max1[i], g[i][j]);
            }        
        }
        ans2 = max(ans2, max1[i]);
    }
    double ans = INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] > INF / 2) {
                ans = min(ans, max1[i] + max1[j] + get_dis(store[i], store[j]));
            }
        }
    }
    
    printf("%.6lf", max(ans, ans2));
    return 0;
}

One more question

Given a sheet  LL  A little bit 、PP  Directed graph of strip edge , Each point has a weight  f[i]f[i], Each edge has a weight  t[i]t[i].

Find a ring in a graph , send “ The sum of the weights of the points on the ring ” Divide “ The sum of the weights of the edges on the ring ” Maximum .

Output the maximum value .

Be careful ： Data guarantees that there is at least one ring .

Input format

The first line contains two integers  LL  and  PP.

Next  LL  Each row is an integer , Express  f[i]f[i].

Next  PP  That's ok , Three integers per row  a,b,t[i]a,b,t[i], Indication point  aa  and  bb  There is an edge between , The weight of the edge is  t[i]t[i].

Output format

Output a number to represent the result , Keep two decimal places .

Data range

2≤L≤10002≤L≤1000,
2≤P≤50002≤P≤5000,
1≤f[i],t[i]≤10001≤f[i],t[i]≤1000

sample input ：

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

sample output ：

6.00

01 Score planning problem , 

I'm mainly not good at using md To write , Then I will give a general description of ,

First of all, I see that the score is the largest , Consider dichotomy , Then according to the given data range , Consider the boundary of dichotomy , Then transform the formula , Finally, we can put ∑ extracted , In this way, we can add the point weight to the edge , Guarantee ∑（wf[i] - mid *wt[i]) > 0, That is, on this ring ∑（wf[i] - mid *wt[i]) Positive value , Finally, finding the existence of a positive ring can make the left boundary become mid, Finally, output the boundary

// In fact, I feel I'm not very transparent , But I generally understand  

Write the code