spfa求调,只过了#2,其他输出impossible
  • 板块P2083 找人
  • 楼主en_en_
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/28 19:25
  • 上次更新2024/7/28 20:49:55
查看原帖
spfa求调,只过了#2,其他输出impossible
1085699
en_en_楼主2024/7/28 19:25
#include<bits/stdc++.h>
using namespace std;
const int N=200001;
struct node{int v,nxt,val;}e[N];
int cnt=0,head[N];
void add(int u,int v,int val){e[++cnt].v=v;e[cnt].val=val;e[cnt].nxt=head[u];head[u]=cnt;}
int vis[N],pre[N],dis[N];
bool spfa(int s,int t){
	memset(vis,0,sizeof(vis));memset(dis,0x7f,sizeof(dis));
	queue<int> q;pre[t]=-1;
	q.push(s),vis[s]=1,dis[s]=0;
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].val){
				dis[v]=dis[u]+e[i].val;pre[v]=u;
				if(!vis[v])vis[v]=1,q.push(v);
			}
		}
	}
	return pre[t]!=-1;
}
int n,m,x,y,v;
struct edge{int x,y;}a[N];
int main(){
	cin>>n>>m>>v>>x>>y;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>a[j].x>>a[j].y;
			add((i-1)*m+j,(a[j].x-1)*m+a[j].y,abs(a[j].x-i)*v);
		}
	int p=(x-1)*m+y;
	if(spfa(1,p))cout<<dis[p];
	else cout<<"impossible";
	return 0;
}
2024/7/28 19:25
加载中...