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】注意：起点需要特别考虑：起点不需要换成时间
推荐阅读
- UVA 10763
- 729uva海明距离问题
- 搜索技术|UVA10054 The Necklace——欧拉回路（DFS）
- POJ|POJ 1364 King 差分约束系统 SPFA
- 四分树（ Quadtrees, UVa 297）
- UVA 108 Maximum Sum (最大子矩阵和) POJ 1050
- UVa, 11000 Bee
- UVA|uva 589 - Pushing Boxes(双重bfs）
- UVA 589 - Pushing Boxes（BFS+状态判重）
- 趣学英语（防晒霜上的spf和uva是什么意思（））