[luogu4162 SCOI2009] 最长距离（最短路）

Solution

题目是最长路，其实是最短路ヽ(ー_ー)ノ

把进入障碍点的边设为1，其他为0。枚举每个点为起点找距离<=T的点，更新答案

Code

//By Menteur_Hxy

#include <queue>

#include <cmath>

#include <cstdio>

#include <vector>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define Re register

#define Ms(a,b) memset(a,(b),sizeof(a))

#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)

#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

inline LL read() {

	LL x=0,f=1;char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int N=31;

int n,m,t;

double ans;

bool vis[N*N];

int mp[N*N],dis[N*N][N*N];

char s[N];

vector <int> V[N*N];

inline int id(int x,int y) {return x*m+y-m;}

inline void add(int x,int y) {V[x].push_back(y);}

priority_queue <PII,vector<PII>,greater<PII> >Q;

void Dij(int S,int *d) {

	Ms(vis,0);

	Q.push(PII(d[S]=0,S));

	while(!Q.empty()) {

		int u=Q.top().second,v; Q.pop();

		if(vis[u]) continue; vis[u]=1;

		int siz=V[u].size();

		Fo(i,0,siz-1) if(d[(v=V[u][i])]>d[u]+mp[v])

			Q.push(PII(d[v]=d[u]+mp[v],v));

	}

}

int main() {

	n=read(),m=read(),t=read();

	Fo(i,1,n) {

		scanf("%s",s+1);

		Fo(j,1,m) mp[id(i,j)]=s[j]-'0';

	}

	Fo(i,1,n) Fo(j,1,m) {

            if(i>1) add(id(i-1,j),id(i,j));

            if(j>1) add(id(i,j-1),id(i,j));

            if(i<n) add(id(i+1,j),id(i,j));

            if(j<m) add(id(i,j+1),id(i,j));

        }

	Ms(dis,0x3f);

	Fo(i,1,n) Fo(j,1,m) Dij(id(i,j),dis[id(i,j)]);

	Fo(x1,1,n) Fo(y1,1,m) if(!mp[id(x1,y1)])

		Fo(x2,1,n) Fo(y2,1,m) if(dis[id(x1,y1)][id(x2,y2)]<=t)

			ans=max(ans,(double)sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)));

	printf("%.6lf",ans);

	return 0;

}

巴特西

[luogu4162 SCOI2009] 最长距离（最短路）

Solution

Code

最新文章

热门文章