一萬兩千年前，精靈還是在艾薩拉女王的統治下，辛德拉是女王手 下一名很有地位的法師。他受任建造了一座城市，來保存女王的法師們進行魔法研究的成果和法術物品。這個城市就是埃雷薩拉斯。永恆之井的爆炸，使這裏的精靈 和總部聯繫中斷，並失去了永恆之井的水做爲能量的來源。辛德拉的後人爲了滿足魔法的慾望，捕獵了一個惡魔，伊莫塔爾，並以水晶塔建造了一個帶有能量平衡係 統的結界監獄，水晶塔從惡魔身上吸取能量，一部分維持結界監獄，一部分可以讓精靈狂熱者吸收。近萬年平安無事。但是現在，惡魔的能量被消耗得越來越多，最 終變得不穩定，已經難以維持結界監獄的消耗。統治這裏的托爾塞林王子開始下令屠殺。只有少數狂熱者之外的其他人都要死，以減少魔法能量的消耗。
終於，強大的戈多克食人魔入侵了埃雷薩拉斯，並殺死了大量的精靈。他們把這裏當作他們的領地，叫做厄運之槌。面臨滅頂之災的精靈們把他們祖先留下的寶藏用魔法結界藏了起來，以防戈多克食人魔搶走。
作爲一名勇敢的探險者，你悄悄來到了埃雷薩拉斯，來尋找傳說中的寶藏。終於，你看到了寶藏，他就在你的前方不遠處。但是你不能貿然前進，因爲路上有着強大的魔法結界。這些結界根據能量的不同分爲P種，踏入每種結界，你都會受到一定的傷害。爲了拿到寶藏，這些傷害算不了什麼。但是你要儘可能地減少傷害，請你設計一條路綫，使你穿越結界獲取寶藏受到的傷害最少。
下面是一個魔法結界能量示意圖，結界是一個正方形，內部有P種不同的能量，每種字母表示一種能量。你從最上端開始走，每次能走到與你所在的位置鄰接的一個單元格，或者在同種能量結界中任意傳送。重複進入同一種能量結界不會再次受到傷害。
|AAABBC|
|ABCCCC|
|AABBDD|
|EEEEEF|
|EGGEFF|
|GGFFFF|
你有H點生命值，請你在貿然行動之前先判斷是否能夠活着（生命值大於0）穿越結界拿到寶藏，如果能夠，請求出最大的生命值。
輸入格式
第1行 三個非負整數 N P H。N爲結界的邊長，P爲不同的能量結界的數量，H爲你的生命值。
第2-P+1行 每行一個非負整數，表示走到該種能量結界受到的傷害值。
第P+2至第P+2+N行 每行N個正整數，爲地圖上該單元格的能量種類的編號，編號爲1..P。
輸出格式
如果你能夠穿越結界到達對岸的寶藏，輸出最多剩餘的生命值。如果不能穿越，輸出NO。
樣例輸入
6 7 10
3
1
2
2
1
1
3
1 1 1 2 2 3
1 2 3 3 3 3
1 1 2 2 4 4
5 5 5 5 5 6
5 7 7 5 6 6
7 7 6 6 6 6
樣例輸出
7
樣例說明
路綫爲
起始-2-5-6-目標
1 1 1 2 2 3
1 2 3 3 3 3
1 1 2 2 4 4
5 5 5 5 5 6
5 7 7 5 6 6
7 7 6 6 6 6
數據規模
對於40%數據
4<=N<=10
對於100%數據
4<=N<=50
1<=P<=N*N
0<=H<=200000000
【分析】
搜索+最短路，把每個結界縮成一個點，通過搜索找出與每個結界相鄰接的結界，就這樣構圖就行了。然後用Dijkstra等O(N^2)算法求最短路即可。
【我的代碼】
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN=2505;
const int MAX=0x7fffffff;
int Mat[MAXN][MAXN];
int Val[MAXN][MAXN];
int Abut[MAXN]={0};
bool used[MAXN][MAXN];
bool flag[MAXN]={false};
int dist[MAXN];
int Map[62][62];
int step[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int N,P,H,E;
int Magic[62];
void init()
{
scanf("%d %d %d",&N,&P,&H);
E=P+1;
for (int i=1;i<=P;i++)
scanf("%d",&Magic[i]);
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
scanf("%d",&Map[i][j]);
for (int i=1;i<=P;i++)
for(int j=1;j<=P;j++)
used[i][j]=false;
bool used[MAXN];
memset(used,false,sizeof(used));
for (int i=1;i<=N;i++)
used[Map[1][i]]=true;
for (int i=1;i<=P;i++)
{
if(used[i])
{
Abut[0]++;
Mat[0][Abut[0]]=i;
Val[0][Abut[0]]=Magic[i];
}
}
memset(used,false,sizeof(used));
for (int i=1;i<=N;i++)
used[Map[N][i]]=true;
for (int i=1;i<=P;i++)
{
if(used[i])
{
Abut[i]++;
Mat[i][Abut[i]]=E;
Val[i][Abut[i]]=0;
}
}
return;
}
void CreatGraph()
{
int nx,ny;
int nc;
for (int k=1;k<=P;k++)
{
for (int i=1;i<=N;i++)
{
for (int j=1;j<=N;j++)
{
if(Map[i][j]!=k)
continue;
for (int m=0;m<4;m++)
{
nx=i+step[m][0];
ny=j+step[m][1];
if(nx<1 || nx>N || ny<1 || ny>N)
continue;
nc=Map[nx][ny];
if(nc!=k && !used[k][nc] && nc!=-1)
{
Abut[k]++;
Mat[k][Abut[k]]=nc;
Val[k][Abut[k]]=Magic[nc];
used[k][nc]=true;
Abut[nc]++;
Mat[nc][Abut[nc]]=k;
Val[nc][Abut[nc]]=Magic[k];
used[nc][k]=true;
}
}
Map[i][j]=-1;
}
}
}
}
void Dijkstra(int S)
{
for (int i=0;i<=E;i++)
{
dist[i]=MAX;
flag[i]=false;
}
for(int i=1;i<=Abut[S];i++)
{
dist[Mat[S][i]]=Val[S][i];
}
dist[S]=0;
flag[S]=1;
for(int i=0;i<=E;i++)
{
int tmp=MAX;
int u=S;
for (int j=0;j<=E;j++)
{
if(!flag[j] && dist[j]<tmp)
{
u=j;
tmp=dist[j];
}
}
flag[u]=1;
for (int j=0;j<=Abut[u];j++)
{
if(!flag[Mat[u][j]])
{
int newdist=dist[u]+Val[u][j];
if(newdist<dist[Mat[u][j]])
{
dist[Mat[u][j]]=newdist;
}
}
}
}
}
int main()
{
freopen("eldrethalas.in","r",stdin);
freopen("eldrethalas.out","w",stdout);
init();
CreatGraph();
Dijkstra(0);
int res=dist[E];
if(res<H)
{
res=H-res;
printf("%d\n",res);
}
else
printf("NO\n");
return 0;
}
【評測結果】
正在连接评测机...
已连接到评测机
| GRID | 1 |
| 名称 | Flitty |
| 系统版本 | 1.00 |
| 备注 | COGS 1号评测机 Flitty |
编译成功
| 测试点 | 结果 | 得分 | 运行时间 | 内存使用 | 退出代码 |
| 1 | 正确 | 10 | 0.000 s | 55463 KB | 0 |
| 2 | 正确 | 10 | 0.091 s | 55463 KB | 0 |
| 3 | 正确 | 10 | 0.000 s | 55463 KB | 0 |
| 4 | 正确 | 10 | 0.000 s | 55463 KB | 0 |
| 5 | 正确 | 10 | 0.001 s | 55463 KB | 0 |
| 6 | 正确 | 10 | 0.001 s | 55463 KB | 0 |
| 7 | 正确 | 10 | 0.019 s | 55463 KB | 0 |
| 8 | 正确 | 10 | 0.065 s | 55463 KB | 0 |
| 9 | 正确 | 10 | 0.080 s | 55463 KB | 0 |
| 10 | 正确 | 10 | 0.080 s | 55463 KB | 0 |
运行时间 0.338 s
平均内存使用 55463 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
