锐客网

  1. 首页 > it技术 > >

uva|uva 10801 SPFA

#include using namespace std; typedef pairpii; priority_queue, greater > q; const int N = 105; const int INF = 1E9; int n, k, T[6], w[N][N], arr[N], d[N]; bool vis[N]; inline void read() { for (int i = 0; i < N; i++) { w[i][i] = INF; for (int j = i + 1; j < N; j++) w[i][j] = w[j][i] = INF; } for (int i = 0; i < n; i++) cin >> T[i]; char ch; for (int i = 0; i < n; i++) { int pos = 0; do { cin >> arr[pos++]; } while (cin.get() != '\n'); for (int j = 0; j < pos; j++) for (int k = j; k < pos; k++) { int tmp = abs(arr[j] - arr[k]) * T[i]; if (tmp < w[arr[j]][arr[k]]) w[arr[j]][arr[k]] = w[arr[k]][arr[j]] = tmp; } } }inline void SPFA(int src) { memset(vis, 0, sizeof(vis)); for (int i = 0; i < N; i++) d[i] = INF; d[src] = 0; queueq; q.push(src); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = 0; i < N; i++) if (u == 0) { if (d[i] > d[u] + w[u][i]) { d[i] = d[u] + w[u][i]; if (!vis[i]) { vis[i] = true; q.push(i); } } } else if (d[i] > d[u] + w[u][i] + 60) { d[i] = d[u] + w[u][i] + 60; if (!vis[i]) { vis[i] = true; q.push(i); } } } }int main(int argc, char const *argv[]) { while (cin >> n >> k) { read(); SPFA(0); if (d[k] != INF) cout << d[k] << endl; else cout << "IMPOSSIBLE" << endl; } return 0; }



求最短路spfa
【uva|uva 10801 SPFA】注意：起点需要特别考虑：起点不需要换成时间

    推荐阅读


    上一篇：complicated|complicated page procedure query

    下一篇：js函数中使用el表达式传入多个参数时的问题