sicily 1321 dijkstra

//优先队列+dijkstra //很久没写图生疏了 //输入处理麻烦一点，有权棋盘两点间最短路，没个棋格都有一个权值 #include<iostream> #include<cstring> #include<queue> #include<cstdio> #include<vector> #define INF 9999999999 using namespace std; int sa[] = { -1,1,0,0 }; int sb[] = { 0,0,-1,1 }; int n,m; int a,b,c,d; bool _used[10010]; struct Node { int p; int key; int path; }node[10010]; bool operator > ( Node a,Node b ) { return a.path > b.path; } priority_queue< Node,vector<Node>,greater<Node> > q; // <<要分开否则VCC compile error int main() { //freopen("1.txt","r",stdin); int tt; cin>>tt; while( tt-- ) { while( !q.empty() ) q.pop(); cin>>n>>m; memset( _used,false,sizeof( _used ) ); for( int i = 0;i < n*m;i++ ) { scanf("%d",&node[i].key); node[i].path = INF; node[i].p = i; } scanf("%d%d%d%d",&a,&b,&c,&d); a--;b--;c--;d--; int _a = a*n+b; int _b = c*n+d; if( _a == _b ) { cout<<node[_a].key<<endl; continue; } node[_a].path = node[_a].key; _used[_a] = true; for( int i = 0;i < 4;i++ ) { if( a + sa[i] >= 0 && a + sa[i] < n && b + sb[i] >= 0 && b + sb[i] < m ) { c = (a+sa[i]) * m + b + sb[i]; node[c].path = node[c].key; q.push(node[c]); } } while( !q.empty() ) { Node pp = q.top(); //加边 q.pop(); int _p = pp.p; if( _used[_p] ) continue; if( _p == _b ) { cout<< node[_b].path + node[_a].path<<endl; break; } _used[_p] = true; a = _p/m;b = _p%m; for( int i = 0;i < 4;i++ ) { if( a + sa[i] >= 0 && a + sa[i] < n && b + sb[i] >= 0 && b + sb[i] < m ) { c = (a+sa[i]) * m + b + sb[i]; if( node[c].path > pp.path + node[c].key ) { node[c].path = pp.path + node[c].key; q.push( node[c] ); } } } } } return 0; }