广告：
#include <stdio.h>
int main()
{
puts("转载请注明出处[vmurder]谢谢");
puts("网址：blog.csdn.net/vmurder/article/details/44064091");
}题意：
从样例讲起。
第1行 s，t，m表示：出发点，终点，m条航线。
然后m组，每组第1行len，n表示这条航线的代价，
这类似于公交车，只要用了就花这些钱，但是用多少都这些钱。
注意是单向边。
举例：
2333 4
3 2 1 4
就是3->2、3->1、3->4、2->1、2->4、1->4都花2333元。
这个花消是第1键值。
第2键值是经过几站。
比如3->2->1->4花费2333
而如果有其它航线使得3->5->4花费1000+1333==2333的话，
那末由于它经过了2站，所以更优。
然后求双键值最短路。
输出这俩键值。
无解输出“⑴ ⑴”。
题解：
裸最短路。
代码：
#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;
}
波比源码 » 【BZOJ3889】【Usaco2015 Jan】Cow Routing 双键值最短路
