我的算法是把每个点拆成两个,[0]左脚踩和[1]右脚踩,然后连边,写了个最朴素的Dij求最短路：

long sx[2][9] = {1, 1, 1, 1, 1, 2, 2, 2, 3, -1, -1, -1, -1, -1, -2, -2, -2, -3};
long sy[9] = {2, 1, 0, -1, -2, 1, 0, -1, 0};
n=w*h;
while (true) {
                k = n;
                k1 = 0;
                min = MAXIUM;
                for (i=0;i<n;++i) {
                    for (j=0;j<2;++j) {
                        if (!stat[i][j] && dis[i][j]<min) {
                           k = i;
                           k1 = j;
                           min = dis[i][j];
                        }
                    }
                }
                if (k==n || t[k])
                   break;
                stat[k][k1] = true;
                j1 = k1;
                k1 = (k1+1)%2;
                x = k%w;
                y = k/w;
                for (i=0;i<9;++i) {
                    y1 = y+sy[i];
                    x1 = x+sx[k1][i];
                    if (x1>=0 && x1<w && y1>=0 && y1<h) {
                       j = y1*w+x1;
                       if (!stat[j][k1] && dis[j][k1]>dis[k][j1]+c[j]) {
                          dis[j][k1] = dis[k][j1]+c[j];
                       }
                    }
                }
          }

结果TLE，TLE，又TLE，再TLE，还是TLE……
崩溃~后来写了个只在当前拓展过的节点中找最小值的（……多写了100+行），A了~600多MS。
感觉这题数据量不是很大，n=30*60=1800,最朴素的Dij也只不过O(n^2)，10^6而已，怎么会T呢？

• Re:最朴素的Dijstra咋就过不了啊? -_-~ (11) amisleeping 2007-08-09 11:14:22
• ElogV (1454) lunatic 2007-08-09 16:59:30