题意： gym上题面有错误，方向有四种。 一个方格，4种方向走，有点不能走，有黑洞传送并且改变时间，求起点到终点最短时间。同时判断可不可能时间无限小或者到不了。
思路： 直接spfa判负环。
#include <iostream> #include <string> #include <cstring> #include <cstdio> #include <vector> #include <queue> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 1005; vector<pair<int,int>>G[maxn]; int dirx[] = {0,0,1,-1}; int diry[] = {1,-1,0,0}; int vis[maxn],mp[maxn],d[maxn],cnt[maxn]; int n,m; int f(int i,int j) { return i * m + j; } void build() { int q;scanf("%d",&q); for(int i = 1;i <= q;i++) { int x1,y1,x2,y2,t;scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&t); vis[f(x1,y1)] = -1; G[f(x1,y1)].push_back({f(x2,y2),t}); } vis[f(n - 1,m - 1)] = -1; for(int i = 0;i < n;i++) { for(int j = 0;j < m;j++) { if(vis[f(i,j)]) continue; if(i == n - 1 && j == m - 1) continue; for(int d = 0;d < 4;d++) { int dx = i + dirx[d]; int dy = j + diry[d]; if(vis[f(dx,dy)] == 1) continue; if(dx < 0 || dy < 0 || dx >= n || dy >= m || vis[f(dx,dy)] == 1 || vis[f(i,j)] == 1) continue; G[f(i,j)].push_back({f(dx,dy),1}); } } } } int spfa() { memset(d,INF,sizeof(d)); memset(cnt,0,sizeof(cnt)); memset(mp,0,sizeof(mp)); d[0] = 0; mp[0] = 1; queue<int>q;q.push(0); while(!q.empty()) { int now = q.front();q.pop(); mp[now] = 0; if(++cnt[now] > n * m) { return -INF; } for(int i = 0;i < G[now].size();i++) { int v = G[now][i].first,w = G[now][i].second; if(d[v] > d[now] + w && vis[v] != 1) { d[v] = d[now] + w; if(!mp[v]) { mp[v] = 1; q.push(v); } } } } return d[f(n - 1,m - 1)]; } int main() { int kase = 0; while(~scanf("%d%d",&n,&m) && n && m) { for(int i = 0;i < 1000;i++) G[i].clear(); memset(vis,0,sizeof(vis)); int q;scanf("%d",&q); for(int i = 1;i <= q;i++) { int x,y;scanf("%d%d",&x,&y); vis[f(x,y)] = 1; } build(); int ans = spfa(); if(ans == -INF) printf("Never\n"); else if(ans == INF) printf("Impossible\n"); else printf("%d\n",ans); } return 0; }