POJ3114强连通+spfa

最新推荐文章于 2020-02-08 23:39:45 发布

京城一十三

最新推荐文章于 2020-02-08 23:39:45 发布

阅读量530

点赞数

分类专栏： ACM_最短路 ACM_强连通

本文链接：https://blog.csdn.net/u013761036/article/details/44308389

版权

ACM_最短路同时被 2 个专栏收录

30 篇文章

订阅专栏

ACM_强连通

9 篇文章

订阅专栏

题意：
给你n个点，m条有向边，q询问，每次询问给两个数a,b输出a->b的最短路，但是题目有个限制，就是在一个环上的任意两点距离为0.

思路：
简单题目，直接强连通压缩点，之后一遍spfa就行了。

#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>

#define N_node 500 + 5
#define N_edge 500 * 500 + 50
#define INF 1000000000

using namespace std;

typedef struct
{
int to ,next ,cost;
}STAR;

typedef struct
{
int a ,b ,c;
}EDGE;

STAR E1[N_edge] ,E2[N_edge];
EDGE E[N_edge];
int list1[N_node] ,list2[N_node] ,tot;
int Belong[N_node] ,s_x[N_node] ,cont;
int mark[N_node];
stack<int>sk;

void add(int a ,int b ,int c)
{
E1[++tot].to = b;
E1[tot].cost = c;
E1[tot].next = list1[a];
list1[a] = tot;

E2[tot].to = a;
E2[tot].cost = c;
E2[tot].next = list2[b];
list2[b] = tot;
}

void DFS1(int s)
{
mark[s] = 1;
for(int k = list1[s] ;k ;k = E1[k].next)
{
int to = E1[k].to;
if(!mark[to]) DFS1(to);
}
sk.push(s);
}

void DFS2(int s)
{
mark[s] = 1;
Belong[s] = cont;
for(int k = list2[s] ;k ;k = E2[k].next)
{
int to = E2[k].to;
if(!mark[to]) DFS2(to);
}
}

void Spfa(int s ,int n)
{
memset(mark ,0 ,sizeof(mark));
for(int i = 0 ;i <= n ;i ++)
s_x[i] = INF;
queue<int>q;
q.push(s);
mark[s] = 1;
s_x[s] = 0;
while(!q.empty())
{
int xin ,tou;
tou = q.front();
q.pop();
mark[tou] = 0;
for(int k = list1[tou] ;k ;k = E1[k].next)
{
xin = E1[k].to;
if(s_x[xin] > s_x[tou] + E1[k].cost)
{
s_x[xin] = s_x[tou] + E1[k].cost;
if(!mark[xin])
{
mark[xin] = 1;
q.push(xin);
}
}
}
}
}

int main ()
{
int n ,m, q;
while(~scanf("%d %d" ,&n ,&m) && n + m)
{
memset(list1 ,0 ,sizeof(list1));
memset(list2 ,0 ,sizeof(list2));
tot = 1;
for(int i = 1 ;i <= m ;i ++)
{
scanf("%d %d %d" ,&E[i].a ,&E[i].b ,&E[i].c);
add(E[i].a ,E[i].b ,E[i].c);
}
while(!sk.empty()) sk.pop();
memset(mark ,0 ,sizeof(mark));
for(int i = 1 ;i <= n ;i ++)
if(!mark[i]) DFS1(i);
memset(mark ,0 ,sizeof(mark));
cont = 0;
while(!sk.empty())
{
int i = sk.top();
sk.pop();
if(mark[i])continue;
++cont;
DFS2(i);
}
//printf("%d****\n" ,cont);
memset(list1 ,0 ,sizeof(list1));
memset(list2 ,0 ,sizeof(list2));
tot = 1;
for(int i = 1 ;i <= m ;i ++)
{
int a ,b ,c;
a = E[i].a ,b = E[i].b ,c = E[i].c;
if(Belong[a] == Belong[b])continue;
add(Belong[a] ,Belong[b] ,c);
}
scanf("%d" ,&q);
while(q--)
{
int a ,b;
scanf("%d %d" ,&a ,&b);
if(Belong[a] == Belong[b]) printf("0\n");
else
{
Spfa(Belong[a] ,cont);
int sx = s_x[Belong[b]];
if(sx == INF) printf("Nao e possivel entregar a carta\n");
else printf("%d\n" ,sx);
}
}printf("\n");
}
return 0;
}