POJ 3114 Tarjan+Dijkstra

題意：

間諜在戰争期間想要傳遞一份諜報回國，諜報可以在郵局之間傳遞，但這種傳遞是單向的，并且會少耗一些時間。但是如果兩個郵局在同一個國家的話，那麼諜報在這兩個郵局之間傳遞是不消耗時間的。如果幾個郵局發出的諜報可以通過一些路徑互相到達，那麼這些郵局就屬于一個國家。那麼問題來了：給出一個起點和終點，問最快什麼時候能夠将諜報傳遞到。

思路：

先Tarjan縮點，然後跑Dijkstra（Floyd可能會被卡，但是貌似有個哥們【現在應該叫前輩了】多交了幾次，卡1000ms過了）（也可以記憶化搜尋，spfa什麼的 看個人喜好吧…）

原題請戳這裡

#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dfn[],low[],p[],map[][],MAP[][],W[],n,m,t,cnt;
bool vis[],VIS[];
vector<int>v[];
stack<int>stk;
void tarjan(int x)
{
    vis[x]=;stk.push(x);low[x]=dfn[x]=++cnt;
    for(int i=;i<v[x].size();i++)
        if(!dfn[v[x][i]])
            tarjan(v[x][i]),low[x]=min(low[x],low[v[x][i]]);
        else if(vis[v[x][i]])
            low[x]=min(low[x],dfn[v[x][i]]);
    if(low[x]==dfn[x]){
        t++;int jy;
        do jy=stk.top(),stk.pop(),p[jy]=t,vis[jy]=;while(jy!=x);
    }
}
int dijkstra(int start,int end)
{
    memset(VIS,,sizeof(VIS));
    for(int i=;i<=t;i++)
        W[i]=MAP[start][i];
    VIS[start]=;
    for(int i=;i<t;i++)
    {
        int minn=,k=-;
        for(int j=;j<=t;j++)
            if(minn>W[j]&&!VIS[j])
                minn=W[j],k=j;
        VIS[k]=;
        for(int j=;j<=t;j++)
            if(!VIS[j]&&W[j]>W[k]+MAP[k][j])
            W[j]=W[k]+MAP[k][j];
    }
    return W[end]<?W[end]:-;
}
int main()
{
    while(scanf("%d%d",&n,&m)&&n)
    {
        cnt=t=;
        memset(map,,sizeof(map));
        memset(MAP,,sizeof(MAP));
        memset(dfn,,sizeof(dfn));
        memset(vis,,sizeof(vis));
        memset(p,,sizeof(p));
        for(int i=;i<=n;i++)v[i].clear();
        for(int i=;i<=n;i++)map[i][i]=MAP[i][i]=;
        for(int i=;i<=m;i++)
        {
            register int xx,yy,weight;
            scanf("%d%d%d",&xx,&yy,&weight);
            v[xx].push_back(yy);
            if(weight<map[xx][yy])map[xx][yy]=weight;
        }
        for(int i=;i<=n;i++)
            if(!dfn[i])tarjan(i);
        for(int i=;i<=n;i++)
            for(int j=;j<v[i].size();j++)
                if(p[i]!=p[v[i][j]])
                MAP[p[i]][p[v[i][j]]]=min(MAP[p[i]][p[v[i][j]]],map[i][v[i][j]]);
        scanf("%d",&m);
        for(int i=;i<=m;i++)
        {
            register int xx,yy;
            scanf("%d%d",&xx,&yy);
            if(p[xx]==p[yy])printf("0\n");
            else
            {
                 int jy=dijkstra(p[xx],p[yy]);
                 if(jy==-)printf("Nao e possivel entregar a carta\n");
                 else printf("%d\n",jy);
            }
        }
        printf("\n");
    }
}
           

就是這位前輩，卡1000ms過的。。

Dijkstra還是快點兒的。