開始noip得訓(xùn)練主要是因?yàn)榈玫揭环菁媛毠ぷ?，給小朋友們講課=。=

退役了一年多，沒碰過算法的老咸魚為了不誤人子弟還是抽時(shí)間訓(xùn)練起來吧。

不得不說，中文題真的爽啊，比acm要開心多了。

image

image

說來慚愧。

我的第一反應(yīng)就是暴搜。。。

然后寫著寫著發(fā)現(xiàn)有點(diǎn)最短路的意思？

用priority_queue記錄到每個(gè)點(diǎn)用的最少花費(fèi)，空白點(diǎn)只可能是神奇魔法來的，但是它后面的點(diǎn)必須有顏色。所以我單獨(dú)開了一個(gè)東西記錄現(xiàn)在這個(gè)點(diǎn)的顏色，而輸入的數(shù)組不動(dòng)，以用來看上一步的各自是被魔法來的顏色還是本身就有的。
其他的和dijkstra最短路幾乎一樣。因?yàn)槭莾?yōu)先隊(duì)列，所以每個(gè)點(diǎn)進(jìn)入隊(duì)列一次就可以，后面來的肯定是花費(fèi)更多了。（所以我加了num數(shù)組，就算不加也不會(huì)影響結(jié)果，但是會(huì)慢一丟丟，畢竟一些沒有用的點(diǎn)進(jìn)到了隊(duì)列里。）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> pi;
typedef pair<pi,pi> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
const int maxn = 110;
int n,m,t1,t2,t3,a[maxn][maxn];
int vis[maxn][maxn],ans = -1,num[maxn][maxn];
int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};

void init(){
    scanf("%d%d",&m,&n);
    for(int i = 0 ; i < n ; i++){
        scanf("%d%d%d",&t1,&t2,&t3);
        a[t1][t2] = t3+1;
    }
}
void sov(){
    q.push(make_pair(make_pair(0,a[1][1]),(make_pair(1,1))));
    memset(vis,-1,sizeof(vis));
    num[1][1] = 1;
    while(!q.empty()){
        pii node = q.top(),node2;
        q.pop();
        int cost = node.first.first;
        int col = node.first.second;
        int x = node.second.first;
        int y = node.second.second;
        if(vis[x][y] != -1 && vis[x][y] > cost) vis[x][y] = cost;
        else if(vis[x][y] == -1)   vis[x][y] =cost;
        else continue;

        for(int i = 0;i < 4; i++){
            int nextx = x+dir[i][0];
            int nexty = y+dir[i][1];
            if(a[x][y] == 0 && a[nextx][nexty] == 0)    continue;
            if(nextx < 1||nexty < 1 || nextx > m || nexty > m||num[nextx][nexty])  continue;
            if(a[nextx][nexty] == 0){
                node2.first.first = cost+2;
                node2.first.second = col;
            }
            else if(a[nextx][nexty] == col){
                node2.first.first = cost;
                node2.first.second = col;
            }
            else{
                node2.first.first = cost+1;
                node2.first.second = a[nextx][nexty];
            }
            node2.second.first = nextx;
            node2.second.second = nexty;
            q.push(node2);

            num[nextx][nexty]++;
        }
    }
    printf("%d\n",vis[m][m]);
}
int main(){
    init();
    sov();
}