POJ 3114 Countries in War 強連通+最短路

POJ 3114 Countries in War 強連通+最短路

#include
#include
#include
using namespace std;
#include
const int INF =1999299;
int minn(int a,int b)
{
    return a>b?b:a;
}
#define N 510
#define M  251000
int n, m;//n m 為點數和邊數
struct Edge
{
    int from, to, val,nex;
    bool sign;//是否為橋
} edge[M<<1];
int head[N], edgenum;
void add(int u, int v,int val) //邊的起點和終點
{
    Edge E= {u, v, val,head[u], false};
    edge[edgenum] = E;
    head[u] = edgenum++;
}
int DFN[N], Low[N], Stack[N], top, Time; //Low[u]是點集{u點及以u點為根的子樹} 中(所有反向弧)能指向的(離根最近的祖先v) 的DFN[v]值(即v點時間戳)
int taj;//連通分支標號，從1開始
int Belong[N];//Belong[i] 表示i點屬於的連通分支
bool Instack[N];
vector bcc[N]; //標號從1開始

void tarjan(int u ,int fa)
{
    DFN[u] = Low[u] = ++ Time ;
    Stack[top ++ ] = u ;
    Instack[u] = 1 ;
    for (int i = head[u] ; ~i ; i = edge[i].nex )
    {
        int v = edge[i].to;
        if(DFN[v] == -1)
        {
            tarjan(v , u);
            Low[u] = minn(Low[u] ,Low[v]) ;
            if(DFN[u] < Low[v])
            {
                edge[i].sign = 1;//為割橋
            }
        }
        else if(Instack[v])
        {
            Low[u] = minn(Low[u] ,DFN[v]) ;
        }
    }
    if(Low[u] == DFN[u])
    {
        int now;
        taj ++ ;
        bcc[taj].clear();
        do
        {
            now = Stack[-- top] ;
            Instack[now] = 0 ;
            Belong [now] = taj ;
            bcc[taj].push_back(now);
        }
        while(now != u) ;
    }
}

void tarjan_init(int all)
{
    memset(DFN, -1, sizeof(DFN));
    memset(Instack, 0, sizeof(Instack));
    top = Time = taj = 0;
    for(int i=1; i<=all; i++)
        if(DFN[i]==-1 )
            tarjan(i, i); //注意開始點標！！！
}
vectorG[N];
int du[N];
void suodian()
{
    memset(du, 0, sizeof(du));
    for(int i = 1; i <= taj; i++)
        G[i].clear();
    for(int i = 0; i < edgenum; i++)
    {
        int u = Belong[edge[i].from], v = Belong[edge[i].to];
        if(u!=v)
        {
            G[u].push_back(v), du[v]++;
        }
    }
}
int d[N][N],cost[N][N];
void Dijkstra(int n,int beg)
{
    bool vis[N];
    for(int i=0; i<=n; i++)
    {
        d[beg][i]=INF;
        vis[i]=false;
    }
    d[beg][beg]=0;
    for(int j=1; j<=n; j++)
    {
        int k=-1;
        int Min=INF;
        for(int i=0; i<=n; i++)
            if(!vis[i]&&d[beg][i]