• 欢迎光临~

# P3057 [USACO12NOV]Distant Pastures S [Dijkstra]

https://www.luogu.com.cn/problem/P3057

```#include <bits/stdc++.h>
using namespace std;
int n, s, p, x, y, h[910], dis[910], vis[910];
char a[35][35];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
struct node{
int x, y, z, next;
}d[7510];
struct edge{
int p, d;
bool operator < (const edge &A) const{
return A.d < d;
}
};
void add(int x, int y, int z){
d[++p].y = y, d[p].z = z, d[p].next = h[x], h[x] = p;
}
void dijkstra(int s){
memset(vis, 0, sizeof(vis));
memset(dis, 9, sizeof(dis));
priority_queue <edge> q;
q.push((edge){s, 0});
dis[s] = 0;
while (!q.empty()){
edge T = q.top(); q.pop();
if (vis[T.p]) continue; vis[T.p] = 1;
for (int i=h[T.p]; i; i=d[i].next){
int sy = d[i].y;
if (dis[sy] > dis[T.p] + d[i].z){
dis[sy] = dis[T.p] + d[i].z; q.push((edge){sy, dis[sy]});
}
}
}
}
int main(){
scanf ("%d%d%d", &n, &x, &y);
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
cin >> a[i][j];
}
}
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
for (int k=0; k<4; k++){
int nx = i + dx[k], ny = j + dy[k];
if (nx <= 0 || ny <= 0 || nx > n || ny > n) continue;
if (a[nx][ny] == a[i][j]) add((i-1)*n+j, (nx-1)*n+ny, x);
}
}
}
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
dijkstra((i-1)*n+j);
for (int k=1; k<=n; k++){
for (int l=1; l<=n; l++){
s = max(s, dis[(k-1)*n+l]);
}
}
}
}
printf ("%dn", s);
return 0;
}```