Question 1 - Go to school
Question description
City C can be regarded as\(n\)nodes and\(m\)An undirected graph composed of edges. These nodes are in turn\(1,2,…,n\)Marking, edges in sequence\(1,2,…,m\)Marking number. The\(i\)Strip edge (\(1≤i≤m\)) The connection number is\(u_i\)and\(v_i\)The node of\(l_i\)rice.
The school of Little A is located in the city C. The school is numbered\(s\)node. Little A's classmates have\(q\)They want to go out to school as late as possible every day without ensuring they are not late. But the students didn't know how long it would take to get from home to school, so they found the smart little A. The\(i\)A classmate (\(1≤i≤q\)) Tell Xiao A that his home is located at\(h_i\)and he can walk every second\(1\)rice. Please help Xiao A calculate how many seconds it takes for each student to get to school from home?
Input format
The first line, four positive integers\(n,m,s,q\), respectively represent the number of nodes and edges in City C, the node number where the school is located, and the number of students A.
Next\(m\)Row, three positive integers per line\(u_i,v_i,l_i\), indicates an undirected edge in City C.
Next\(q\)Line, one positive integer per line\(h_i\), indicating the situation of a classmate.
Output format
common\(q\)Yes, for each student, output an integer, indicating the shortest time to start from home to school.
Sample
Enter sample 1
5 5 3 3
1 2 3
2 3 2
3 4 1
4 5 3
1 4 2
5
1
4
Output sample 1
4
3
1
Data range
for\(20\%\)Test points, guarantee\(q=1\)。
For other\(20\%\)Test points, guarantee\(1≤n≤500，1≤m≤500\)。
For all test points, guarantee\(1≤n≤2×10^5，1≤m≤2×10^5，1≤q≤2×10^5\)，\(1≤u_i,v_i,s,h_i≤n，1≤l_i≤10^6\). Ensure that the given diagram is connected.
analyze
This question is actually very simple, it is a naked shortest-circuit problem. We just need to start from the end point and run backwards. It is very simple.
#include<bits/stdc++.h>
using namespace std;
const int INF=2e5+10;
struct Node{
long long v,num;
bool operator <(const Node &a)const{
return num>;
}
};
vector<Node> mp[INF];
long long dis[INF],used[INF];
priority_queue<Node> q;
void dijkstra(int x){
dis[x]=0,({x,0});
while (!()){
long long u=().v;();
if (used[u]==1)continue;
used[u]=1;
int len=mp[u].size();
for (int i=0;i<len;i++){
long long v=mp[u][i].v,w=mp[u][i].num;
if (dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
({v,dis[v]});
}
}
}
}
int main(){
int n,m,s,q;
cin>>n>>m>>s>>q;
for (int i=1;i<=n;i++){
dis[i]=1e18;
}
for (int i=1;i<=m;i++){
long long u,v,l;
cin>>u>>v>>l;
mp[u].push_back({v,l});
mp[v].push_back({u,l});
}
dijkstra(s);
for (int i=1;i<=q;i++){
int t;
cin>>t;
cout<<dis[t]<<endl;
}
return 0;
}
advertise
Shortest Circuit Algorithm—CSDN
Shortest Circuit Algorithm—Blog Garden
Question 2 - Split
Question description
Xiao Yang has a tree containing\(n\)The tree of nodes, where the node number is from\(1\)arrive\(n\)。
Xiao Yang has set up\(a\)A good point is right<\(u_1\),\(v_1\)>,<\(u_2\),\(v_2\)>,...,<\(u_a\),\(v_a\)> and 1 bad point <\(b_u\),\(b_v\)>. A node can be deleted if and only if:
After deleting the node, all\(i(1≤i≤a)\), good point\(u_i\)and\(v_i\)Still connected;
The bad point pair after deleting this node\(b_u\)and\(b_v\)Not connected.
If any node in the point pair is deleted, it is considered to be non-connected.
Xiao Yang wanted to know how many nodes could be deleted.
Input format
The first line contains two positive integers\(n,a\), the meaning is as shown in the title.
after\(n−1\)rows, each row contains two positive integers\(x_i,y_i\), means there is a connection node\(x_i\)and\(y_i\)the edge.
after\(a\)rows, each row contains two positive integers\(u_i,v_i\), represents a good point <\(u_i,v_i\)>。
The last line contains two positive integers\(b_u,b_v\), represents bad points <\(b_u,b_v\)>。
Output format
Output a positive integer, representing the number of nodes that can be deleted.
Sample
Enter sample
6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6
Output sample
2
Data range
For all data, guarantee\(1≤n≤10^6,0≤a≤10^5,ui≠vi,bu≠bv\)。
analyze
This question actually has some thinking content. According to the question, we need to know that those points can be deleted and those points cannot be deleted. Based on this, we need to maintain that each point has been passed by those points, or has been passed several times. If a point has not passed by any good points and has been passed by the bad points, then it means that this point can be deleted. The good point passing I am talking about here refers to the path between two good points. Don't make a mistake.
If this is the way we think, can we obviously think of a way, difference in the tree? And this is a very short answer point difference, so it's okay to say that there is no difficulty.
#include<bits/stdc++.h>
using namespace std;
const int INF=1e6+10;
vector<int> mp[INF];
int dp[INF][30],deep[INF],p[INF],d[INF];
void prepare(int x,int fa){
for (int i=1;(1<<i)<=deep[x]-1;i++){
dp[x][i]=dp[dp[x][i-1]][i-1];
}
int len=mp[x].size();
for (int i=0;i<len;i++){
if (mp[x][i]==fa)continue;
int t=mp[x][i];
dp[t][0]=x,deep[t]=deep[x]+1;
prepare(t,x);
}
}
int getroot(int x,int y){
if (deep[x]<deep[y])swap(x,y);
int index=__lg(deep[x]-deep[y]);
for (int i=index;i>=0;i--){
if (deep[dp[x][i]]>=deep[y])x=dp[x][i];
if (deep[x]==deep[y])break;
}
if (x==y)return x;
for (int i=20;i>=0;i--){
if (dp[x][i]!=dp[y][i])x=dp[x][i],y=dp[y][i];
}
return dp[x][0];
}
void get_p(int x,int fa){
int len=mp[x].size();
for (int i=0;i<len;i++){
if (mp[x][i]==fa)continue;
int t=mp[x][i];
get_p(t,x);
p[x]+=p[t];
}
}
void get_d(int x,int fa){
int len=mp[x].size();
for (int i=0;i<len;i++){
if (mp[x][i]==fa)continue;
int t=mp[x][i];
get_d(t,x);
d[x]+=d[t];
}
}
int main(){
int n,a;
cin>>n>>a;
for (int i=1;i<n;i++){
int u,v;
cin>>u>>v;
mp[u].push_back(v);
mp[v].push_back(u);
}
deep[1]=1;
prepare(1,-1);
for (int i=1;i<=a;i++){
int u,v;
cin>>u>>v;
int root=getroot(u,v);
p[u]++,p[v]++,p[root]--,p[dp[root][0]]--;
}
get_p(1,-1);
int b1,b2;
cin>>b1>>b2;
int root=getroot(b1,b2);
d[b1]++,d[b2]++,d[root]--,d[dp[root][0]]--;
get_d(1,-1);
int cnt=0;
for (int i=1;i<=n;i++){
if (d[i]&&!p[i])cnt++;
}
cout<<cnt;
return 0;
}
Summarize
This time the eighth grade questions are not difficult, but the previous multiple-choice and judgment questions CCF was wrong, so it was delayed a little time. For people with better foundation, this set of eighth grade questions can be completed within 1 and a half hours (it only took about 1 hour for a konjac like me)