您當前位置：首頁 > php開源 > php教程 > 【BZOJ3889】【Usaco2015 Jan】Cow Routing 雙鍵值最短路

【BZOJ3889】【Usaco2015 Jan】Cow Routing 雙鍵值最短路

來源：程序員人生發(fā)布時間：2015-03-17 09:11:49 閱讀次數(shù)：2647次

題意：

從樣例講起。
第1行 s，t，m表示：出發(fā)點，終點，m條航線。

然后m組，每組第1行l(wèi)en，n表示這條航線的代價，
這類似于公交車，只要用了就花這些錢，但是用多少都這些錢。
注意是單向邊。

舉例：
2333 4
3 2 1 4
就是3->2、3->1、3->4、2->1、2->4、1->4都花2333元。

這個花消是第1鍵值。
第2鍵值是經(jīng)過幾站。

比如3->2->1->4花費2333
而如果有其它航線使得3->5->4花費1000+1333==2333的話，
那末由于它經(jīng)過了2站，所以更優(yōu)。

然后求雙鍵值最短路。
輸出這倆鍵值。

無解輸出“⑴ ⑴”。

題解：

裸最短路。

代碼：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1010
#define INF 0x3f3f3f3f3f3f3f3fll
using namespace std;
long long map[N][N];
int dist[N][N];
int id[N],cnt;
int s,t,m;
int n,a[N],c;

long long dis[N];
int di[N];
bool in[N];
queue<int>q;
void spfa()
{
    memset(dis,0x3f,sizeof dis);
    memset(di,0x3f,sizeof di);
    int i,u;
    q.push(s),in[s]=1;
    di[s]=dis[s]=0;
    while(!q.empty())
    {
        u=q.front(),q.pop();
        for(i=1;i<=cnt;i++)if(map[u][i]<INF)
        {
            if(dis[i]==dis[u]+map[u][i])
            {
                di[i]=min(di[i],di[u]+dist[u][i]);
                if(!in[i])in[i]=1,q.push(i);
            }
            else if(dis[i]>dis[u]+map[u][i])
            {
                dis[i]=dis[u]+map[u][i];
                di[i]=di[u]+dist[u][i];
                if(!in[i])in[i]=1,q.push(i);
            }
        }
    }
    return ;
}
int main()
{
    memset(map,0x3f,sizeof map);
    memset(dist,0x3f,sizeof dist);
    int i,j,k;
    scanf("%d%d%d",&s,&t,&m);
    if(s==t)
    {
        puts("0 1");
        return 0;
    }
    s=id[s]=cnt=1;
    t=id[t]=cnt=2;

    while(m--)
    {
        scanf("%d%d",&c,&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(!id[a[i]])id[a[i]]=++cnt;
            a[i]=id[a[i]];
        }
        for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)
        {
            if(map[a[i]][a[j]]==c)
                if(dist[a[i]][a[j]]>j-i)
                    dist[a[i]][a[j]]=j-i;
            if(map[a[i]][a[j]]>c)
            {
                map[a[i]][a[j]]=c;
                dist[a[i]][a[j]]=j-i;
            }
        }
    }
    for(i=1;i<=cnt;i++)map[i][i]=0,dist[i][i]=0;

    spfa();
    if(dis[t]==INF)puts("⑴ ⑴");
    else printf("%lld %d
",dis[t],di[t]);

    return 0;
}