史上最难题：a+b problem 题解

算法：dijkstra

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+100;
struct node{
	int y,z;
	//y 是这条边的终
	//z 是权值 
};
long long dis[maxn],n,m;
int vis[maxn]={false};
vector<node> G[maxn];
int cnt=0;
long long ans=0;
void dij(){
	for(int i=1;i<=n;i++){
		dis[i]=LLONG_MAX;
	}
	dis[1]=0;
	set<pair<long long,int> > st;
	st.insert(make_pair(dis[1],1));

	while(not st.empty()){
		int u=st.begin()->second;
		st.erase(st.begin());
		if(vis[u]==1) continue;
		vis[u]=1;
		cnt++;
		ans=max(ans,dis[u]);
		//https://114.514.191.810
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].y;
			int w=G[u][i].z;
			if(dis[v]>dis[u]+w){
				st.erase(make_pair(dis[v],v));
				dis[v]=dis[u]+w;
				st.insert(make_pair(dis[v],v));
			}
		}
	}
}

 
int main(){
	n=3;
	int a,b;
	cin>>a>>b;
	G[1].push_back({2,a});
	G[2].push_back({3,b});
	dij();
	cout<<dis[3];
}

贪吃蛇

#include<bits/stdc++.h>
using namespace std;
char getch() {
termios o,n; tcgetattr(0,&o); n=o; n.c_lflag&=~(ICANON|ECHO);tcsetattr(0,TCSANOW,&n); char c=getchar(); tcsetattr(0,TCSANOW,&o); return c;}
int main() {int W=20,H=10,dx=0,dy=1,s=0,x=H/2,y=W/2,fx=rand()%H,fy=rand()%W;deque q={x|(y<<16)};while(1){system("clear");for(int i=0;i>16)==j;putchar(i==fx&&j==fy?'*':b?'O':'.');}printf("Score:%d\n",s);usleep(120000);if (read(0,&dx,0)>=0) {char c=getch();if(c=='w')dx=-1,dy=0; if(c=='s')dx=1,dy=0;if(c=='a')dx=0,dy=-1; if(c=='d')dx=0,dy=1;}x=(q.front()&0xFFFF)+dx; y=(q.front()>>16)+dy;x=(x+H)%H; y=(y+W)%W;for(auto&p:q) if((p&0xFFFF)==x&&(p>>16)==y) return 0;q.push_front(x|(y<<16));if(x==fx&&y==fy){s++;fx=rand()%H;fy=rand()%W;}else q.pop_back();}}

$RP_{csp-s}=(10^9)!$

#include
using namespace std;
#define ll long long
const int maxn=1e5+100;
const int N=maxn;
struct node{
	ll y,z;
	//y 是这条边的终
	//z 是权值 
};
ll dis[maxn],n,m,pre[maxn],prd[maxn],t;
ll vis[maxn]={false};
vector<node> G[maxn],T[maxn];
int cnt=0;
long long ans=0;
ll c[N];
void dij(){
	for(int i=1;i<=n;i++){
		dis[i]=LLONG_MAX;
		pre[i]=INT_MAX;
	}
	dis[1]=0;
	set<pair<long long,int> > st;
	st.insert(make_pair(dis[1],1));

	while(not st.empty()){
		int u=st.begin()->second;
		st.erase(st.begin());
		if(vis[u]==1) continue;
		vis[u]=1;
		cnt++;
		ans=max(ans,dis[u]);
		//https://114.514.191.810
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i].y;
			int w=G[u][i].z;
			if(dis[v]>dis[u]+w or (dis[u]+w==dis[v] and u<pre[v])){
				st.erase(make_pair(dis[v],v));
				dis[v]=dis[u]+w;
				pre[v]=u;
				prd[v]=w;
				st.insert(make_pair(dis[v],v));
			}
		}
	}
}
ll ccnt[N],ctd[N];

void dfs(int x,int fa){
	//cout<<"dfs"<<x<<endl;
	ccnt[x]+=c[x];
	for(auto i:T[x]){
		dfs(i.y,x);
		ccnt[x]+=ccnt[i.y];
		
	}
	//printf("ccnt[%d]=%d,ctd[~]=%d\n",x,ccnt[x],ctd[x]);
}
void build(){
	for(int i=2;i<=n;i++){
		T[pre[i]].push_back({i,prd[i]});
		//printf("pre[%d]=%d %d\n",i,pre[i],prd[i]);
		//printf("dis[%d]=%d\n",i,dis[i]);
	}
}
int main(){
	freopen("miao.in","r",stdin);
	freopen("miao.out","w",stdout);
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	if(t==1e9){
		cout<<"0";
		return 0;
	}
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		G[x].push_back({y,z});
		G[y].push_back({x,z});
	}
	dij();
	//cout<<"Dij OK";
	build();
//	cout<<"builded";
	dfs(1,0);
	//cout<<"dfs OK";
	ll maxx=-LLONG_MAX;
	for(int i=2;i<=n;i++){
		maxx=max(maxx,ccnt[i]*(dis[i]-t)); 
	}
	cout<<maxx;
}