极值你太美

userId_undefined

我爱编程 编程不爱我

倔强青铜

2024-10-12 21:07:59

发布于：北京

693阅读
0回复
0点赞
https://www.acgo.cn/contest/detail/4614?matchRoundId=4614&examId=47257&teamCode=1661232050350374912&openLevel=2

ic6D



#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define NN 1001
int N,M,X;
int e[NN][NN],book[NN],dis[NN];
int dis1[NN],dis2[NN];
int mi;
void Dijkstra()
{
	memset(book,0,sizeof(book));
	for(int i=1; i<=N; i++)
		dis[i]=e[X][i];
	book[X]=1;
	int u;
	for(int i=1; i<N; i++)
	{
		mi=INF;
		for(int j=1; j<=N; j++)
		{
			if(book[j]==0&&dis[j]<mi)
			{
				mi=dis[j];
				u=j;
			}
		}
		book[u]=1;
		for(int k=1; k<=N; k++)
		{
			if(dis[k]>dis[u]+e[u][k])  //松弛操作
				dis[k]=dis[u]+e[u][k];
		}
	}
}
int main()
{
	cin>>N>>M>>X;/*N头牛，M条道路，目的地为X*/
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=N; j++)
		{
			if(i==j)
				e[i][j]=0;
			else
				e[i][j]=INF;
		}
	}
	for(int i=0; i<M; i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(e[a][b]>c)
			e[a][b]=c;
	}
	Dijkstra();
	for(int i=1; i<=N; i++)
		dis1[i]=dis[i];
	for(int i=1; i<=N; i++)
		for(int j=i+1; j<=N; j++)
			swap(e[i][j],e[j][i]);
	Dijkstra();
	for(int i=1; i<=N; i++)
		dis2[i]=dis[i];
	int mx=-1;
	for(int i=1; i<=N; i++)
	{
		if(dis1[i]+dis2[i]>mx)
			mx=dis1[i]+dis2[i];
	}
	cout<<mx;
	return 0;
}





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

const int maxn = 1e3 + 9;
struct node {
	long long v, w;
};
vector<node> ve[2][maxn];
long long d[maxn];
bool vis[maxn];
int n, m;
void dijkstra(int s) {
	memset(d, 0x3f, sizeof(d));
	memset(vis, 0, sizeof(vis));
	d[1] = 0;
	for (int i = 1; i < n; i++) {
		int id = -1;
		for (int j = 1; j <= n; j++) {
			if(!vis[j]){
				if(id == -1 || d[id] > d[j]) id = j;
			}
		}
		if (id == -1) break;
		vis[id] = 1;
		for (int j = 0; j < ve[s][id].size(); j++) {
			int y = ve[s][id][j].v, w = ve[s][id][j].w;
			if (d[y] > d[id] + w) {
				d[y] = d[id] + w;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		ve[0][u].push_back({ v,w });
		ve[1][v].push_back({ u,w });
	}
	long long ans = 0;
	dijkstra(0);
	for (int i = 1; i <= n; i++) ans += d[i];
	dijkstra(1);
	for (int i = 1; i <= n; i++) ans += d[i];
	cout << ans;
	return 0;
}






#include<bits/stdc++.h>
using namespace std;
int to[8][2]= {-2,1,-1,2,1,2,2,1,1,-2,2,-1,-1,-2,-2,-1};
bool vis[209][209];
int n,m;
string mp[209];
int bx,by,ex,ey;
struct node
{
	int x,y;
	int step;
};
queue<node>q;
void bfs(){
	node u,v;
	u.x=bx,u.y=by,u.step=0;
	vis[bx][by]=true;
	q.push(u);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		if(u.x==ex&&u.y==ey)  //走到终点
		{
			cout<<u.step;
			return;
		}
		for(int i=0; i<8; i++)
		{
			v.x=u.x+to[i][0];
			v.y=u.y+to[i][1];
			v.step=u.step+1;
			if(v.x>=0&&v.x<n&&v.y>=0&&v.y<m&&vis[v.x][v.y]==false&&mp[v.x][v.y]!='*')
			{
				vis[v.x][v.y]=true;
				q.push(v);
			}
		}
	}
}
int main()
{
	cin>>m>>n; //列 行
	for(int i=0; i<n; i++) //地图
		cin>>mp[i];
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
		{
			if(mp[i][j]=='K')  //起点
			{
				bx=i;
				by=j;
			}
			if(mp[i][j]=='H') //终点
			{
				ex=i;
				ey=j;
			}
		}
	}
	bfs();
	return 0;
}







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

const int maxn = 1e4 + 9;
int heap[maxn], heap_size;
void put(int d) {
	int son, pa;
	heap[++heap_size] = d;//新增一个结点，值为d
	son = heap_size;
	while (son > 1) { //向上调整，使其满足小根堆的性质
		pa = son >> 1; //找到父节点
		if (heap[son] >= heap[pa]) break; //如果父节点的值小于等于儿子结点，调整完毕
		swap(heap[son], heap[pa]);  //向上调整
		son = pa;
	}
}
//返回堆顶的值，并删除堆顶
int get() {
	int pa, son, res;
	res = heap[1]; //存储堆顶的值
	heap[1] = heap[heap_size--]; //用最后一个元素覆盖堆顶，并把堆元素个数减一
	pa = 1;
	//向下调整
	while (pa * 2 <= heap_size) {
		son = pa * 2;
		if (son < heap_size && heap[son + 1] < heap[son]) son++;//找到存在的儿子中最小的一个
		if (heap[pa] <= heap[son]) break; //调整完毕
		swap(heap[pa], heap[son]);//向下调整
		pa = son;
	}
	return res;//返回堆顶的值
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		put(a);
	}
	int ans = 0;
	while (heap_size > 1) {
		int x = get(), y = get();
		ans += x + y;
		put(x + y);
	}
	cout << ans;
	return 0;
}



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

struct node{
	int from , to , len;
};
vector<node>v[505];
int n , m , w , x , y , z;
int d[510];
int main(){
	scanf("%d %d %d",&n,&m,&w);
	for(int i = 2 ; i <= n ; i++){
            d[i] = 1e9;
        }
	for(int i = 0 ; i < m ; i++){
		scanf("%d %d %d",&x , &y , &z);
		v[x].push_back((node){x,y,z});
		v[y].push_back((node){y,x,z});
	}
	for(int i = 0 ; i < w ; i++){
		scanf("%d %d %d",&x,&y,&z);
		v[x].push_back((node){x,y,-z});
	}	
    int from,to,len;
	for(int k = 0 ; k < n ; k++){
		for(int i = 1 ; i <= n ; i++){
			for(int j = 0 ; j < v[i].size() ; j++){
                from = v[i][j].from , to = v[i][j].to , len = v[i][j].len;
                if(d[to] > d[from] + len){
			        d[to] = d[from] + len;
					if(k == n - 1){
					    printf("YES\n");
						return 0;
					}	
				}
			}
		}
	}
	printf("NO\n");
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 24

热门讨论