为帮助大家能在6月18日的比赛中有一个更好的成绩,我会将蓝桥杯官网上的历届决赛题目的四类语言题解都发出来。希望能对大家的成绩有所帮助。
今年的最大目标就是能为【一亿技术人】创造更高的价值。
资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
//#pragma GCC optimize(3)
//#include<bits/stdc++.h>
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<ctime>
#include<cmath>
#include<numeric>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<set>
//#include<unordered_set>
#include<map>
//#include<unordered_map>
#include<bitset>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define ri register int
#define rll register long long
#define INF 0x7f7f7f7f
#define rep(i,begin,end) for(int i=begin;i<=end;++i)
#define REP(i,begin,end) for(int i=begin;i>=end;--i)
#define vi vector<int>
#define vl vector<long long>
#define umap unordered_map
#define uset unordered_set
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(x) x.begin(),x.end()
#define mkp make_pair
#define y1 __y1
#define NL putchar('\n')
#define MSET(a,v) memset(a,v,sizeof(a))
#define MT int __T=RD;while(__T--)
#define BEFORE(__time) while((double)clock()/CLOCKS_PER_SEC<__time)
inline int min(int a,int b,int c){return min(a,min(b,c));}
inline ll min(ll a,ll b,ll c){return min(a,min(b,c));}
inline double min(double a,double b,double c){return min(a,min(b,c));}
inline int max(int a,int b,int c){return max(a,max(b,c));}
inline ll max(ll a,ll b,ll c){return max(a,max(b,c));}
inline double max(double a,double b,double c){return max(a,max(b,c));}
inline int gcd(int a,int b){int aa=a,bb=b;while(bb){int r=aa%bb;aa=bb;bb=r;}return aa;}
inline ll gcd(ll a,ll b){ll aa=a,bb=b;while(bb){ll r=aa%bb;aa=bb;bb=r;}return aa;}
inline int lcm(int a,int b){return a/gcd(a,b)*b;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline int lowbit(int x){return x&(-x);}
inline void print(int x){printf("%d ",x);}
inline void print(ll x){printf("%lld ",x);}
inline void print(double x){printf("%lf ",x);}
inline void print(int* a,int n) {rep(i,1,n)printf("%d ",a[i]);NL;}
inline void print(ll* a,int n) {rep(i,1,n)printf("%lld ",a[i]);NL;}
inline void print(double* a,int n) {rep(i,1,n)printf("%.2lf ",a[i]);NL;}
/*
inline void print(vi& a) {for(auto&v:a)printf("%d ",v);NL;}
inline void print(vl& a) {for(auto&v:a)printf("%lld ",v);NL;}
inline void print(vector<double>& a){for(auto&v:a)printf("%.2lf ",v);NL;}
inline void print(map<int,int>& a) {for(auto it=a.begin(),end=a.end();it!=end;++it)printf("%d %d\n",it->first,it->second);NL;}
inline void print(umap<int,int>& a) {for(auto it=a.begin(),end=a.end();it!=end;++it)printf("%d %d\n",it->first,it->second);NL;}
inline void print(set<int>& a) {for(auto it=a.begin(),end=a.end();it!=end;++it)printf("%d ",it);NL;}
inline void print(uset<int>& a) {for(auto it=a.begin(),end=a.end();it!=end;++it)printf("%d ",it);NL;}
*/
#define PR print
inline int read1(){ri x=0;ri c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+(c^48),c=getchar();return x;}
inline ll read2(){rll x=0;ri c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10L+(c^48),c=getchar();return x;}
inline int read3(){ri x=0;ri c=getchar();int f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+(c^48),c=getchar();return x*f;}
inline ll read4(){rll x=0;ri c=getchar();ll f=1L;while(c<'0'||c>'9'){if(c=='-')f=-1L;c=getchar();}while(c>='0'&&c<='9')x=x*10L+(c^48),c=getchar();return x*f;}
#define RD read1()
#define _DIR_COUNT 0
#if (_DIR_COUNT==4)
const int dx[]={-1, 1, 0, 0}; //上下左右
const int dy[]={ 0, 0,-1, 1};
#elif (_DIR_COUNT==8)
const int dx[]={-1,-1, 0, 1, 1, 1, 0,-1}; //从上方顺时针
const int dy[]={ 0, 1, 1, 1, 0,-1,-1,-1};
#endif
const int N=2002;
int n,m,k,t;
int tim[N],type[N];
int f[N];
vector<pii>e[N];
void dfs(int p){
if(f[p]!=-1)return;
f[p]=0;
int sz=e[p].size();
int mi=INT_MAX;
for(int i=0;i<sz;++i){
int a=e[p][i].first,b=e[p][i].second;
dfs(a);dfs(b);
mi=min(mi,
max(f[a],f[b])+max(tim[a],tim[b])
);
}
if(mi!=INT_MAX)f[p]+=mi;
}
int main(){
memset(f,-1,sizeof(f));
n=RD;m=RD;k=RD;t=RD;
rep(i,1,n)tim[i]=RD;
rep(i,1,m)type[i]=RD;
rep(i,1,k){
int a=RD,b=RD,c=RD;
e[c].push_back({a,b});
}
dfs(t);
printf("%d",f[t]);
return 0;
}
#include<stdio.h>
int n=0;//作物类型总数
int m=0;//拥有作物种数
int k=0;//杂交方案数
int t=0;// 目标种子编号
int N[2005]={0};//每种作物杂交天数
int M[2005]={0};//表示已有的种子类型 1 有 0 没有
int K[100005][3]={0};//方案
int f[2005];
int max(int a, int b){
return a>b?a:b;
}
int min(int a, int b){
return a<b?a:b;
}
void F( int sign ){
int i=0;
int minv = 1e9;
if( f[sign] != -1 ){
return ;
}
f[sign] = 0;
for( i=1; i<=k; i++ ){
if( sign == K[i][2] ){
F( K[i][0] );
F( K[i][1] );
minv = min(minv, max(f[ K[i][0]] , f[ K[i][1] ]) + max(N[ K[i][0] ], N[ K[i][1] ]) );
}
}
if(minv != 1e9) f[sign] += minv;
}
/*
6 2 4 6
5 3 4 6 4 9
1 2
1 2 3
1 3 4
2 3 5
4 5 6
*/
int main(){
int i=0;
memset(f,-1,sizeof f);
scanf("%d %d %d %d",&n,&m,&k,&t);
for( i=1; i<=n; i++ ){
scanf("%d",&N[i]);
}
for( i=1; i<=m; i++ ){
scanf("%d",&M[i]);
}
for( i=1; i<=k; i++ ){ // 0 X 1 == 2
scanf("%d %d %d",&K[i][0],&K[i][1],&K[i][2]);
}
//查找t所需作物
F(t);
printf("%d",f[t]);
return 0;
}
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
static int aa[], dp[];
static List<Point> bh[];
public static void main(String[] args) throws IOException {
StreamTokenizer x = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
x.nextToken();
int n = (int) x.nval;
x.nextToken();
int m = (int) x.nval;
x.nextToken();
int k = (int) x.nval;
x.nextToken();
int t = (int) x.nval;
aa = new int[n + 1];
dp = new int[n + 1];
bh = new List[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
int bb[] = new int[m + 1];
for (int i = 1; i <= n; i++) {
x.nextToken();
aa[i] = (int) x.nval;
bh[i] = new ArrayList<Point>();
}
for (int i = 1; i <= m; i++) {
x.nextToken();
bb[i] = (int) x.nval;
dp[bb[i]] = 0;
}
for (int i = 0; i < k; i++) {
x.nextToken();
int xx = (int) x.nval;
x.nextToken();
int yy = (int) x.nval;
x.nextToken();
int nn = (int) x.nval;
bh[nn].add(new Point(xx, yy));
}
out.println(dfs(t));
out.flush();
}
public static int dfs(int n) {
if (dp[n] != Integer.MAX_VALUE)
return dp[n];
List<Point> p = bh[n];
for (int i = 0; i < p.size(); i++) {
int x = p.get(i).x, y = p.get(i).y;
dp[n] = Math.min(dp[n], Math.max(dfs(x), dfs(y)) + Math.max(aa[x], aa[y]));
}
return dp[n];
}
}
def dfs(u):
if f[u]:return f[u]
L=len(s[u])
if L==0:return 0
f[u]=int(2e9)
for i in range(0,L,2):
f[u]=min(f[u],max(dfs(s[u][i]),dfs(s[u][i+1]))+max(t[s[u][i]-1],t[s[u][i+1]-1]))
return f[u]
n,m,k,tar=map(int,input().split())
t=list(map(int,input().split()))
s=[]
f=[]
for i in range(n+1):
s.append([])
f.append(0)
a=list(map(int,input().split()))
while k:
k-=1
A,B,C=map(int,input().split())
s[C].append(A)
s[C].append(B)
print(dfs(tar))