学步园

题目大意是这样说的，在一个有向图中，每两点间通信需要一定的时间，但同一个强连通分量里传递信息不用时间，给两点u，v求他们最小的通信时间。

思路：题意比较直白，就是缩点后，重新建图，求其最短路。看了一下点的范围是500，查询次数是100，想了一下，用SPFA求最短路时间会快点，但floyd也可以，代码短。最后发现时间有点多。。。。

//2644K    985MS
#include
#include
const int VM = 505;
const int EM = VM*VM;
const int inf = 0x3f3f3f3f;
struct Edge
{
    int to,w,nxt;
}edge[EM];

int head[VM],vis[VM],stack[VM],belong[VM];
int dfn[VM],low[VM],mat[VM][VM];
int ep,cnt,scc,top,n;

int min(int a,int b)
{
    return a > b ? b : a;
}
void addedge (int cu,int cv,int cw)
{
    edge[ep].to = cv;
    edge[ep].w = cw;
    edge[ep].nxt = head[cu];
    head[cu] = ep ++;
}
void Tarjan (int u)
{
    int v;
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1;
    stack[top ++] = u;
    for (int i = head[u];i != -1;i = edge[i].nxt)
    {
        v = edge[i].to;
        if (!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if (vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        ++scc;
        do{
            v = stack[--top];
            vis[v] = 0;
            belong[v] = scc;
        }while (u != v);
    }
}
void solve()
{
    memset (dfn,0,sizeof(dfn));
    memset (vis,0,sizeof(vis));
    memset (mat,0x3f,sizeof(mat));
    scc = top = cnt = 0;
    int u,v;
    for (u = 1;u <= n;u ++)
        if (!dfn[u])
            Tarjan(u);
    for (u = 1;u <= n;u ++)
    {
        for (int i = head[u];i != -1;i = edge[i].nxt)
        {
            v = edge[i].to;
            if (belong[u] != belong[v])
                mat[belong[u]][belong[v]] = min(mat[belong[u]][belong[v]],edge[i].w);
        }
    }
    for (u = 1;u <= scc;u ++) mat[u][u] = 0;
}
void floyd()
{
    for (int k = 1;k <= scc;k ++)
        for (int i = 1;i <= scc;i ++)
            for (int j = 1;j <= scc;j ++)
                if (mat[i][j] > mat[i][k] + mat[k][j])
                    mat[i][j] = mat[i][k] + mat[k][j];
}
int main ()
{
    #ifdef LOCAL
        freopen ("in.txt","r",stdin);
    #endif
    int m,u,v,w;
    while (~scanf ("%d%d",&n,&m)&&n)
    {
        memset (head,-1,sizeof(head));
        ep = 0;
        while (m --)
        {
            scanf ("%d%d%d",&u,&v,&w);
            addedge (u,v,w);
        }
        solve ();
        floyd();
        scanf ("%d",&m);
        while (m --)
        {
            scanf ("%d %d",&u,&v);
            u = belong[u],v = belong[v];
            if (mat[u][v]!= inf)
                printf ("%d\n",mat[u][v]);
            else printf ("Nao e possivel entregar a carta\n");
        }
        printf ("\n");
    }
}