怎么办崩溃了受不了了受不了了小小地接给我整洪文了
查看原帖
怎么办崩溃了受不了了受不了了小小地接给我整洪文了
1065103
Atri_Lobato楼主2024/6/28 22:26
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define Pair pair<unsigned long long int,int>
using namespace std;
int n,m,a,b,c;
unsigned long long int r[1005][1005];
unsigned long long int dis[1005][1005];
struct Mov
{
	int x,y;
}mov[4];
bool ed[1005][1005];
struct loc
{
	int x,y;
}location;
vector<loc> points;
priority_queue <Pair,vector<Pair>,greater<Pair> > que;
void dijkstra(loc start)
{
	while(que.empty()==0)
	que.pop();
	
	memset(dis,127,sizeof(dis));
	memset(ed,0,sizeof(ed));
	points.clear();
//	ed[start.y][start.x]=1;
	dis[start.y][start.x]=0;
	points.push_back(start);
	que.push(make_pair(0,points.size()-1));
	while(que.empty()==0)
	{
		loc now=points[que.top().second];
		int x=now.x;
		int y=now.y;
		que.pop();
		if(ed[y][x]==1)
		{
			continue;
		}
		ed[y][x]=1;
		for(int i=0;i<4;i++)
		{
			loc next;
			next.x=x+mov[i].x;
			next.y=y+mov[i].y;
			if(next.x<1||next.y<1||next.x>m||next.y>n||ed[next.y][next.x]==1)
			continue;
			int nextdis=dis[y][x]+r[next.y][next.x];
			if(dis[next.y][next.x]>nextdis)
			{
				dis[next.y][next.x]=nextdis;
				points.push_back(next);
				que.push(make_pair(nextdis,points.size()-1));
			}
		}
	}
}
int main()
{
	mov[1].x=1;
	mov[1].y=0;
	
	mov[2].x=0;
	mov[2].y=1;
	
	mov[3].x=0;
	mov[3].y=-1;
	
	mov[0].x=-1;
	mov[0].y=0;
	unsigned long long int minn=999999999999999999;
	scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);
	for(int i=1;i<=n;i++)
	{
		for(int q=1;q<=m;q++)
		{
			scanf("%d",&r[i][q]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int q=1;q<=m;q++)
		{
			location.x=q;
			location.y=i;
			dijkstra(location);
			cout<<dis[n][a]+dis[1][b]+dis[1][c]+r[location.y][location.x]<<endl;
			if(minn>dis[n][a]+dis[1][b]+dis[1][c]+r[location.y][location.x])
			{
				minn=dis[n][a]+dis[1][b]+dis[1][c]+r[location.y][location.x];
			}
		}
	}
	cout<<minn;
	return 0;
}
2024/6/28 22:26
加载中...