kuangbin_ShortPath M (POJ 1062)

提出了一个错误的算法 以为能优化到只运行两次dij

然而我还是too naive 还是乖乖dij n 次吧…

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#define INF 0x3F3F3F3F
using namespace std;typedef pair<int, int> pii;
struct cmp{
    bool operator () (const pii a, const pii b){
        return a.first > b.first;
    }
};int map[][], val[][], lev[];
int m, n;int dij()
{
    int  dist[];
    priority_queue<pii, vector<pii>, cmp> q;
    memset(dist, 0x3f, sizeof dist);
    dist[] = ;
    q.push(make_pair(, ));
    while(!q.empty()){
        pii u = q.top();
        q.pop();
        if(u.first > dist[u.second]) continue;
        for(int i = ; i <= n; i++){
            if(dist[i] > dist[u.second] + val[u.second][i]){
                dist[i] = dist[u.second] + val[u.second][i];
                q.push(make_pair(dist[i], i));
            }
        }
    }
    return dist[];
}int main()
{
    memset(map, 0x3f, sizeof val);
    scanf("%d%d", &m, &n);
    for(int i = ; i <= n; i++){
        int x, y, p;
        scanf("%d%d%d", &map[][i], &lev[i], &x);
        while(x--){
            scanf("%d%d", &y, &p);
            map[y][i] = p;
        }
    }
    int ans = INF;
    for(int i = ; i <= m; i++){
        memset(val, 0x3f, sizeof val);
        for(int x =  ; x <= n; x++){
            if(x ==  || (lev[x] >= lev[] - m + i && lev[x] <= lev[] + i)){
                for(int y = ; y <= n; y++){
                    if(lev[y] >= lev[] - m + i && lev[y] <= lev[] + i){
                        val[x][y] = map[x][y];
                    }
                }
            }
        }
        ans = min(dij(), ans);
        //printf("%d ~ %d : %d\n", lev[1] - m + i, lev[1] + i, ans);
    }
    printf("%d\n", ans);
    return ;
}