1128. Messenger
1127. Sweet butter
1128. Messenger
During the war, there are n posts on the front line, and each post may have communication links with several other posts.
Couriers are responsible for delivering messages between outposts, which of course takes a certain amount of time (measured in days).
The headquarters is located at the first post.
When the headquarters issues an order, the headquarters sends several couriers to deliver the message to the outposts connected to the headquarters.
When a post receives a letter, the couriers in this post also deliver the letter to other posts in the same way. The length of time a letter remains in a post is negligible.
The message delivery will not be considered successful until all n outposts have received the order.
Because preparations are sufficient, enough couriers are placed in each outpost (if one outpost is connected to other k
If there is communication contact between two outposts, at least k messengers will be equipped in this outpost).
Now the commander-in-chief asks you to write a program to calculate the shortest time required to complete the entire message delivery process.
Input format
Line 1 contains two integers n and m, separated by a space, indicating n outposts and m communication lines respectively.
Lines 2 to m + 1: Each line contains three integers i, j, k, separated by a space, indicating that there is a two-way communication line between the i-th and j-th posts, and this line costs k sky.
Output format
An integer representing the shortest time to complete the entire sending process.
If not all outposts can receive the letter, output -1.
data range
1≤n≤100
1≤m≤200
1≤k≤1000
Input example:
4 4
1 2 4
2 3 7
2 4 1
3 4 6
Example output:
11
Difficulty: Easy
Time/space limit: 1s/64MB
Total number of passes: 10904
Total attempts: 19519
Source: “Informatics Olympiad Comprehensive Guide”
This question can be viewed as finding the maximum value of the shortest path from a single source to all nodes
The first time each node receives a broadcast should be the time when the message reaches the node along the shortest path from the source (in the context of the problem, only node 1 publishes messages, so it can still be regarded as a single source);
What this question requires is to find the latest time when a node receives a message, that is, the time it takes for all nodes to reach the point with the longest distance from the source point, which is the solution to this question.
Pay attention to a judgment here. In graph theory operations, it is often necessary to initialize arrays or adjacency lists (assign values to positive infinity).
In order to ensure additivity, that is, no overflow dis[j] = dis[u] + g[u][j]; we usually set the initial value to 0x3f , note that the memset assignment method assigns values in bytes, so when assigning to int, each int element will be assigned the value 0x3f3f3f3f instead of 0x3f
//This question does not seem to be a single-source shortest path but a multi-source problem.
#include<bits/stdc + + .h>
using namespace std;
const int N = 110;
const int INF = 0x3f;
int n, m;
int g[N][N];
bool vis[N];
int dis[N];
int dijkstra()
{<!-- -->
int res = 0;
dis[1] = 0;
for(int i = 0;i < n;i + + ){<!-- -->
int u = -1;
for(int j = 1;j <= n;j + + ){<!-- -->
if(!vis[j] & amp; & amp; (u == -1 || dis[j] < dis[u])){<!-- -->
u = j;
}
}
vis[u] = 1;
for(int j = 1;j <= n;j + + ){<!-- -->
if(!vis[j] & amp; & amp; dis[j] > dis[u] + g[u][j]){<!-- -->
dis[j] = dis[u] + g[u][j];
}
}
}
for(int j = 2;j <= n;j + + ) res = max(res, dis[j]);
if(res == 0x3f3f3f3f) res = -1; //A judgment needs to be made here. There is no guarantee that the source point can reach all nodes.
return res;
}
int main()
{<!-- -->
memset(g, INF, sizeof g);
memset(dis, INF, sizeof dis);
cin >> n >> m;
while(m --){<!-- -->
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = c;
}
int ans = dijkstra();
cout << ans << endl;
return 0;
}
1127. Sweet butter
Farmer John discovered the way to make the sweetest butter in Wisconsin: sugar.
Putting sugar on a patch of pasture, knowing that N cows would come and lick it, he could make super-sweet butter that would sell for a good price.
Of course, he will pay extra for the cows.
Farmer John is cunning, like Pavlov before him, and he knows that he can train these cows to go to a specific pasture when they hear a bell.
He planned to put the sugar there and ring it in the afternoon so that he could milk the cows at night.
Farmer John knows that each cow is in his or her own preferred pasture (a pasture does not necessarily have only one cow).
Given the pastures of each cow and the route between pastures, find the shortest distance for all the cows to reach (where he will put the sugar).
The data ensures that there is at least one pasture connected to the pastures where all cattle are located.
Input format
The first row: three numbers: the number of cows N, the number of pastures P, and the number of roads between pastures C.
Line 2 to Line N + 1: Pasture numbers where cows 1 to N are located.
Row N + 2 to Row N + C + 1: Each row has three numbers: connected pastures A and B, and the distance between the two pastures D. Of course, the connection is bidirectional.
Output format
On one line, output the minimum distance the cow must walk.
data range
1≤N≤500
2≤P≤800
1≤C≤1450
1≤D≤255
Input example:
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
Example output:
8
The version I wrote is traversal. All nodes are set as source nodes and calculated once. It can run through some data but TLE.
#include<bits/stdc + + .h>
using namespace std;
const int N = 810;
const int INF = 0x3f;
const int MAX = 0x3f3f3f3f;
int n, m, num;
int g[N][N];
int init[N]; //Record the cows that were initially in i pasture
int dis[N];
int vis[N];
//Take st node (pasture) as the source
int dijkstra(int st)
{<!-- -->
memset(dis, INF, sizeof dis);
memset(vis, 0, sizeof vis);
dis[st] = 0;
for(int i = 0;i < m;i + + ){<!-- -->
int u = -1;
for(int j = 1;j <= m;j + + ){<!-- -->
if(!vis[j] & amp; & amp; (u == -1 || dis[j] < dis[u])){<!-- -->
u = j;
}
}
vis[u] = 1;
if(dis[u] == MAX) return MAX; //At this time, the source node is not guaranteed to be connected.
for(int j = 1;j <= m;j + + ){<!-- -->
if(!vis[j] & amp; & amp; dis[j] > dis[u] + g[u][j]){<!-- -->
dis[j] = dis[u] + g[u][j];
}
}
}
/*
cout << st << endl;
for(int i = 1;i <= m;i + + )
cout << dis[i] <<" ";
cout << endl;*/
int res = 0;
for(int i = 1;i <= m;i + + ){<!-- -->
int x = init[i]; //The number of cows in the current pasture
res + = dis[i] * x;
}
//cout << res << endl;
return res;
}
int main()
{<!-- -->
memset(g, INF, sizeof g);
cin >> n >> m >> num;
for(int i = 1;i <= n;i + + ){<!-- -->
int x; scanf("%d", & amp;x);
init[x] + + ;
}
while(num --){<!-- -->
int a, b, c;
scanf("%d%d%d", & amp;a, & amp;b, & amp;c);
g[a][b] = g[b][a] = c;
}
int ans = MAX;
for(int i = 1;i <= m;i + + ){<!-- -->
ans = min(ans, dijkstra(i));
}
cout << ans;
return 0;
}
Improvement: The time complexity can be optimized in the second level of loop, that is, when finding the closest point, that is, using the heap optimization method to find the closest node
Using adjacency lists to store edges in heap optimization
Adjacency list declaration
int h[N], e[M], w[M], ne[M], idx; //N is the number of nodes, M is the number of edges in h[a] points to the last element of the adjacency list list starting from node a e[idx] is the node pointed by the edge with the current idx number. w[idx] is the weight of the edge with the current idx number ne stores the adjacency list linked list. The current value is the address of the next adjacency list, similar to the value of a pointer. initialization idx = 0; memset(h, -1, sizeof h);
Adjacency list construction
void add(int a, int b, int c) {<!-- -->
e[idx] = b;
w[idx] = c;
//The above two steps construct an edge, which only stores the end point and weight (because the header of the adjacency list is the starting point, no useless information is stored)
ne[idx] = h[a]; //Similar to the head insertion method node->next = L->next (the next pointer of the current node points to the next node of the head node)
h[a] = idx + +; //L->next = node; idx + + Set the next node of the current head node to the current node
}
1. In this construction method, idx is the edge serial number, which serves as the unique identifier of the edge. Once you find idx, you can read the end point information and weight information of the edge.
2. The construction method of the adjacency list is similar to the head interpolation method. h[a] points to the latest entered edge information starting from node a. The value stored is the idx of an edge. The current edge can be obtained through ne[idx]. The idx value of the next edge; ne[idx] == -1 is similar to node->next == NULL. At this time, the tail node of the linked list is traversed
3. If the pointer to the next one is empty, the pointer value is -1
Adjacency list traversal
for(int i = h[vel]; i != -1; i = ne[i]) {<!-- -->
//TODO
}
i = ne[i] simulates the next operation of the linked list pointer
h[vel] points to the last one of the vel linked list, and the traversal is from back to front.
The resulting adjacency list is as follows:
The optimized code is as follows:
#include<bits/stdc + + .h>
using namespace std;
typedef pair<int,int> PII;
const int N = 810; //Number of points
const int M = 3010;
const int INF = 0x3f;
const int MAX = 0x3f3f3f3f;
int n, m, num;
int cow[N]; //Record the initial pasture location of each cow
int h[N], e[M], w[M], ne[M], idx;
bool vis[N];
int dis[N];
void add(int a, int b, int c)
{<!-- -->
e[idx] = b; //The to of this edge is the b node
w[idx] = c; //Change the edge weight to c
ne[idx] = h[a];
h[a] = idx + + ;
}
int dijkstra(int st)
{<!-- -->
memset(vis, 0, sizeof vis);
memset(dis, INF, sizeof dis);
dis[st] = 0;
priority_queue<PII, vector<PII>, greater<PII> >heap;
heap.push({<!-- -->0, st});
while(!heap.empty()){<!-- -->
int u = heap.top().second; //At this time u is the node closest to the source point.
heap.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = h[u]; i != -1; i = ne[i]){<!-- -->
//Find the node connected to u, traverse and update the value of dis
int j = e[i];
if(dis[j] > dis[u] + w[i]){<!-- -->
dis[j] = dis[u] + w[i];
heap.push({<!-- -->dis[j], j});
}
}
}
int ans = 0;
for(int i = 1;i <= n;i + + ){<!-- --> //Calculate the total consumption of N nodes
if(dis[cow[i]] == MAX) return MAX;
ans + = dis[cow[i]];
}
return ans;
}
int main()
{<!-- -->
memset(h, -1, sizeof h);
cin >> n >> m >> num;
for(int i = 1;i <= n;i + + ) cin >> cow[i];
while(num --){<!-- -->
int a, b, c;
scanf("%d%d%d", & amp;a, & amp;b, & amp;c);
add(a, b, c);
add(b, a, c);
}
int ans = MAX;
for(int i = 1;i <= m;i + + ){<!-- -->
ans = min(ans, dijkstra(i));
}
cout << ans << endl;
return 0;
}
The time complexity of heap optimization is lower, and it is suitable for situations where there are many points and few edges (sparse), in which case the adjacency matrix will store a lot of useless information)