建個正向的圖。
建個反向的圖。
2遍spfa搞定。
#include
#include
#include
#include
#include
using namespace std;
int p,q;
const int inf=0x3f3f3f3f;
struct node
{
int v,nxt;
int w;
}edge[1000005];
struct s{
int a,b,c;
}record[1000005];
int nume,head[1000005];
int dis[1000005];
int inque[1000005];
void add(int u,int v,int w)
{
edge[nume].v=v;edge[nume].w=w;edge[nume].nxt=head[u];
head[u]=nume++;
}
int ans=0;
void spfa(int src){
int i;
queueque;
que.push(src);
for(i=1;i<=p;i++) {
dis[i]=inf;
inque[i]=0;
}
dis[src]=0;
inque[src]=1;
while(!que.empty()){
int u=que.front();
que.pop();
inque[u]=0;
for(i=head[u]; i!=-1 ; i=edge[i].nxt){
int v=edge[i].v;
if(dis[u]+edge[i].w
