HDU 2066 - 一个人的旅行
传送门
思路
交了几发Floyd都TLE了，以为过不了的。但是看了别人的题解发现竟然可以过，就加了一个判断mp[i][k]通不通的条件！！优化的力量。
又了解到一个新概念：超级源点
如果要求多个源点到某地的最短路，可以把这几个源点之间的距离看做0，然后任意从一个开始即可。
代码
Floyd
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define LL long long
const int MAXN = 1000 + 5;
const int INF = 0x3f3f3f3f;
int n, mp[MAXN][MAXN], st[MAXN], ed[MAXN], idx, ans;
void Floyd()
{
for (int k = 1; k <= idx; k++)
for (int i = 1; i <= idx; i++)
{
if (mp[i][k] != INF)
for (int j = 1; j <= idx; j++)
{
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
if (st[i] && ed[j])
ans = min(ans, mp[i][j]);
}
}
}
int main()
{
//freopen("input.txt", "r", stdin);
int nr, nwant, i, j, a, b, c;
while (~scanf("%d%d%d", &nr, &n, &nwant))
{
idx = 0;
memset(mp, 0x3f, sizeof mp);
memset(st, 0, sizeof st);
memset(ed, 0, sizeof ed);
for (i = 0; i < nr; i++)
{
scanf("%d%d%d", &a, &b, &c);
mp[a][b] = mp[b][a] = min(c, mp[a][b]);
idx = max(max(a, b), idx);
}
for (i = 1; i <= idx; i++)
mp[i][i] = 0;
for (i = 0; i < n; i++)
{
scanf("%d", &a);
st[a] = 1;
}
for (i = 0; i < nwant; i++)
{
scanf("%d", &a);
ed[a] = 1;
}
ans = INF;
Floyd();
printf("%d\n", ans);
}
return 0;
}
SPFA
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define LL long long
const int MAXN = 1000 + 5;
const int INF = 0x3f3f3f3f;
int n, mp[MAXN][MAXN], st[MAXN], ed[MAXN], idx, ans, d[MAXN];
void SPFA(int start)
{
int vis[MAXN];
memset(vis, 0, sizeof vis);
queue<int> qu;
memset(d, 0x3f, sizeof d);
d[start] = 0;
qu.push(start);
while (!qu.empty())
{
int u = qu.front();
qu.pop();
vis[u] = 0;
for (int i = 1; i <= idx; i++)
{
if (mp[u][i] != INF)
if (d[i] > d[u] + mp[u][i])
{
d[i] = d[u] + mp[u][i];
if (ed[i])
ans = min(ans, d[i]);
if (!vis[i])
{
vis[i] = 1;
qu.push(i);
}
}
}
}
}
int main()
{
//freopen("input.txt", "r", stdin);
int nr, nwant, i, j, a, b, c;
while (~scanf("%d%d%d", &nr, &n, &nwant))
{
idx = 0;
memset(mp, 0x3f, sizeof mp);
memset(st, 0, sizeof st);
memset(ed, 0, sizeof ed);
for (i = 0; i < nr; i++)
{
scanf("%d%d%d", &a, &b, &c);
mp[a][b] = mp[b][a] = min(c, mp[a][b]);
idx = max(max(a, b), idx);
}
for (i = 1; i <= idx; i++)
mp[i][i] = 0;
for (i = 0; i < n; i++)
scanf("%d", &st[i]);
for (i = 0; i < nwant; i++)
{
scanf("%d", &a);
ed[a] = 1;
}
ans = INF;
for (i = 0; i < n; i++)
SPFA(st[i]);
printf("%d\n", ans);
}
return 0;
}
来个邻接表优化呀
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
const int MAXN = 1000 + 5;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
int n, st[MAXN], ed[MAXN], idx, ans, d[MAXN];
vector<pii> mp[MAXN];
void SPFA(int start)
{
int vis[MAXN];
memset(vis, 0, sizeof vis);
queue<int> qu;
memset(d, 0x3f, sizeof d);
d[start] = 0;
qu.push(start);
while (!qu.empty())
{
int u = qu.front();
qu.pop();
vis[u] = 0;
for (int i = 0; i < mp[u].size(); i++)
{
int x = mp[u][i].first;
if (d[x] > d[u] + mp[u][i].second)
{
d[x] = d[u] + mp[u][i].second;
if (ed[x])
ans = min(ans, d[x]);
if (!vis[x])
{
vis[x] = 1;
qu.push(x);
}
}
}
}
}
int main()
{
//freopen("input.txt", "r", stdin);
int nr, nwant, i, j, a, b, c;
while (~scanf("%d%d%d", &nr, &n, &nwant))
{
idx = 0;
for (i = 0; i < MAXN; i++)
mp[i].clear();
//memset(st, 0, sizeof st);
memset(ed, 0, sizeof ed);
for (i = 0; i < nr; i++)
{
scanf("%d%d%d", &a, &b, &c);
mp[a].push_back(MP(b, c)), mp[b].push_back(MP(a, c));
idx = max(max(a, b), idx);
}
for (i = 0; i < n; i++)
scanf("%d", &st[i]);
for (i = 0; i < nwant; i++)
{
scanf("%d", &a);
ed[a] = 1;
}
ans = INF;
for (i = 0; i < n; i++)
SPFA(st[i]);
printf("%d\n", ans);
}
return 0;
}