You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
97 lines
2.7 KiB
C++
97 lines
2.7 KiB
C++
#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;
|
|
} |