LYDSY 1001
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
#include <cstring>
#include <queue>
int pathlen[3000001];
bool inque[3000001];
typedef struct Edge
{
int to, len;
Edge *next;
Edge(int t, int l, Edge *n) : to(t), len(l), next(n) {}
} * lpEdge;
lpEdge G[3000001];
#define addEdge(x, y, z) G[x] = new Edge(y, z, G[x])
#define addEdge2(x, y, z) addEdge(x, y, z), addEdge(y, x, z)
void spfa(int s)
{
std::queue<int> Q;
memset(pathlen, 0x3f, sizeof(pathlen));
memset(inque, 0, sizeof(inque));
inque[s] = true;
pathlen[s] = 0;
Q.push(s);
while (!Q.empty())
{
int x = Q.front();
Q.pop();
inque[x] = false;
for (lpEdge cur = G[x]; cur; cur = cur->next)
if (pathlen[cur->to] > pathlen[x] + cur->len)
{
pathlen[cur->to] = pathlen[x] + cur->len;
if (!inque[cur->to]) inque[cur->to] = true, Q.push(cur->to);
}
}
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
if (n == 1 || m == 1)
if (n == 1 && m == 1)
putchar(0);
else
{
int ans = 0x3f3f3f3f;
for (int i = n > m ? n : m, x; i; i--)
{
scanf("%d", &x);
if (x < ans) ans = x;
}
printf("%d", ans);
}
else
{
int target = (n - 1) * (m - 1) * 2 + 1, x;
for (int i = 1; i < m; i++)
{
scanf("%d", &x);
addEdge2(2 * i, target, x);
}
for (int i = 1; i < n - 1; i++)
for (int j = 1; j < m; j++)
{
scanf("%d", &x);
addEdge2((i - 1) * ((m - 1) << 1) + j * 2 - 1,
i * ((m - 1) << 1) + j * 2, x);
}
for (int i = 1; i < m; i++)
{
scanf("%d", &x);
addEdge2(0, (n - 2) * ((m - 1) << 1) + i * 2 - 1, x);
}
for (int i = 1; i < n; i++)
{
scanf("%d", &x);
addEdge2(0, (i - 1) * ((m - 1) << 1) + 1, x);
for (int j = 1; j < m - 1; j++)
{
scanf("%d", &x);
addEdge2((i - 1) * ((m - 1) << 1) + j * 2,
(i - 1) * ((m - 1) << 1) + j * 2 + 1, x);
}
scanf("%d", &x);
addEdge2(target, i * ((m - 1) << 1), x);
}
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
{
scanf("%d", &x);
addEdge2((i - 1) * ((m - 1) << 1) + (j - 1) * 2 + 1,
(i - 1) * ((m - 1) << 1) + (j - 1) * 2 + 2, x);
}
spfa(0);
printf("%d", pathlen[target]);
}
return 0;
}