hdu 1535 spfa

建个正向的图。

建个反向的图。

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; queue
       
        que; 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