这道题是Dij的变体,由于最大的数据一共是10e6的规模,矩阵一定不过
然后看一下变数,假设每个点发出四条边(上,下, 左,右,这里就包括了双向的边了),那么数据规模就是4*10e6,结构体这样大规模,数组应该是承受不了的,如果用vector的话,应该是可以的,但是还是很麻烦
所以,我们就可以利用两个二维数组来代替边表,因为对于每个点,只要遍历它的上下左右即可
数据结构解决了,那么就是算法实现了,开始直接用的dij,无疑超时了,dij的时间复杂度是N*N,那么也就是10e12的规模,所以后来就用的优先队列来优化
这也是我第一次使用优先队列,发现还是很好用的,按照优先级别来进行优先出队
代码如下:
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int N = 1000; const int INF = 100000000; int g[N][N], cost[N][N]; int T, r, c; struct node { int i, j, w; bool operator < ( const struct node a ) const { return w > a.w; } }tl; void dij() { int mi, ri, ci; bool vis[N][N]; priority_queue <struct node> pq; memset(vis, 0, sizeof(vis)); g[1][1] = cost[1][1]; tl.i = tl.j = 1, tl.w = g[1][1]; pq.push(tl); while ( !pq.empty() ) { tl = pq.top(); pq.pop(); ri = tl.i, ci = tl.j; if ( vis[ri][ci] ) continue; vis[ri][ci] = true; //printf("%d %d\n", ri, ci); if ( ri > 1 && !vis[ri-1][ci] && g[ri-1][ci] > g[ri][ci] + cost[ri-1][ci] ) { g[ri-1][ci] = g[ri][ci] + cost[ri-1][ci]; tl.i = ri-1, tl.j = ci, tl.w = g[ri-1][ci]; pq.push(tl); } if ( ri < r && !vis[ri+1][ci] && g[ri+1][ci] > g[ri][ci] + cost[ri+1][ci] ) { g[ri+1][ci] = g[ri][ci] + cost[ri+1][ci]; tl.i = ri+1, tl.j = ci, tl.w = g[ri+1][ci]; pq.push(tl); } if ( ci > 1 && !vis[ri][ci-1] && g[ri][ci-1] > g[ri][ci] + cost[ri][ci-1] ) { g[ri][ci-1] = g[ri][ci] + cost[ri][ci-1]; tl.i = ri, tl.j = ci-1, tl.w = g[ri][ci-1]; pq.push(tl); } if ( ci < c && !vis[ri][ci+1] && g[ri][ci+1] > g[ri][ci] + cost[ri][ci+1] ) { g[ri][ci+1] = g[ri][ci] + cost[ri][ci+1]; tl.i = ri, tl.j = ci+1, tl.w = g[ri][ci+1]; pq.push(tl); } } } int main() { scanf("%d", &T); while ( T-- ) { scanf("%d%d", &r, &c); for ( int i = 1; i <= r; ++i ) for ( int j = 1; j <= c; ++j ) scanf("%d", &cost[i][j]), g[i][j] = INF; dij(); printf("%d\n", g[r][c]); } }