HDU5521(最短路+建边)
程序员文章站
2022-05-22 14:34:56
...
图论太菜了啊= =。
题解:每个集合外多加一个点,使得集合中的点和这集合外的点连起来,权值为cost,反过来建一条权值为0的边,然后从1跑spfa,从n跑spfa,那最短路就是max(dist1[i],dist2[i])中的最小值。枚举一下就可以
其实挺水的
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <vector>
#define mod 1000000007
#define INF 0x3f3f3f3f
#define fuck() (cout << "----------------------------------------" << endl)
using namespace std;
const int maxn = 2000000 + 5;
int dist1[maxn];
int dist2[maxn];
int queuenum[maxn];
bool vis[maxn];
int n,m;
struct Edge
{
int to;
int cost;
Edge(){}
Edge(int To, int Cost)
{
to = To;
cost = Cost;
}
};
vector <Edge> edge[maxn];
void init()
{
for(int i=0; i<maxn; i++)
edge[i].clear();
memset(dist1,INF,sizeof(dist1));
memset(dist2,INF,sizeof(dist2));
}
void addedge(int from, int to, int cost)
{
edge[from].push_back(Edge(to,cost));
}
void spfa1(int source)
{
memset(vis,false,sizeof(vis));
memset(queuenum,0,sizeof(queuenum));
dist1[source] = 0;
queue < int > q;
q.push(source);
vis[source] = true;
queuenum[source] = 1;
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int i=0; i<edge[u].size(); i++)
{
Edge eg = edge[u][i];
int to = eg.to;
int cost = eg.cost;
if(dist1[u] + cost < dist1[to])
{
dist1[to] = dist1[u] + cost;
if(!vis[to])
{
q.push(to);
queuenum[to]++;
if(queuenum[to] >= n+m)
return;
vis[to] = true;
}
}
}
}
return;
}
void spfa2(int source)
{
memset(vis,false,sizeof(vis));
memset(queuenum,0,sizeof(queuenum));
dist2[source] = 0;
queue < int > q;
q.push(source);
vis[source] = true;
queuenum[source] = 1;
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int i=0; i<edge[u].size(); i++)
{
Edge eg = edge[u][i];
int to = eg.to;
int cost = eg.cost;
if(dist2[u] + cost < dist2[to])
{
dist2[to] = dist2[u] + cost;
if(!vis[to])
{
q.push(to);
queuenum[to]++;
if(queuenum[to] >= n+m)
return;
vis[to] = true;
}
}
}
}
return;
}
int main()
{
int T, kases = 1;
scanf("%d",&T);
while(T--)
{
init();
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int v,num,pt;
scanf("%d%d",&v,&num);
for(int j=0; j<num; j++)
{
scanf("%d",&pt);
addedge(pt,i+n,v);
addedge(i+n,pt,0);
}
}
spfa1(1);
spfa2(n);
int maxcost = INF;
for(int i=1; i<=n; i++)
{
int c = max(dist1[i],dist2[i]);
if(c < maxcost)
maxcost = c;
}
printf("Case #%d: ",kases++);
if(maxcost == INF)
{
printf("Evil John\n");
continue;
}
printf("%d\n",maxcost);
bool flag = true;
for(int i=1; i<=n; i++)
{
int c = max(dist1[i],dist2[i]);
if(c == maxcost)
{
if(flag) printf("%d",i);
else printf(" %d",i);
flag = false;
}
}
printf("\n");
}
return 0;
}
下一篇: Activity之间经典切换动画效果