1.USACO08JAN Telephone Lines 题面
由于问的是最大值最小，所以二分加验证就好了
比较显然的，题干问的是第k+1长的路最短；
那么二分答案是正确的方向；
但是怎么验证？
我们可以将所有边权大于二分的答案的边视为边权是1，否则看成0；
然后从1~n跑最短路，如果答案大于二分的答案那么就不成立，否则成立；
这种思维比较重要，代码还是很简单的；
#include <bits/stdc++.h>
using namespace std;
int head[2000010],cnt;
class littlestar{
public:
int to;
int nxt;
int w;
void add(int u,int v,int gg){
nxt=head[u];
to=v;
w=gg;
head[u]=cnt;
}
}star[2000010];
int n,p,k;
int dis[100010],vis[100010];
bool SPFA(int x)
{
queue<int> q;
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
memset(vis,0,sizeof(vis));
q.push(1);
while(q.size()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(dis[v]>dis[u]+(star[i].w>x)){
dis[v]=dis[u]+(star[i].w>x);
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
if(dis[n]<=k) return 1;
else{
return 0;
}
}
int main()
{
cin>>n>>p>>k;
for(int i=1;i<=p;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
star[++cnt].add(u,v,w);
star[++cnt].add(v,u,w);
}
int l=0,r=1000000;
while(l<r){
int mid=(l+r)/2;
if(SPFA(mid)){
r=mid;
}
else{
l=mid+1;
}
}
if(l==1000000) l=-1;
cout<<l<<endl;
}
这道题很上一道题不太一样，所求的是对于每种方案去掉前k大边后的最短路；
首先由于k很小，可以进行分层图；
第i层图表示目前已经删去了i条边的最短路；
对于点对(i,j)在任意层中边权是w；从第i层到第i+1层的边权是0；
然后堆优化+dijkstra就可以了；
#include <bits/stdc++.h>
using namespace std;
int head[5000010],cnt;
class littlestar{
public:
int to;
int nxt;
int w;
void add(int u,int v,int gg){
nxt=head[u];
to=v;
w=gg;
head[u]=cnt;
}
}star[5000010];
int n,p,k;
int dis[5000010],vis[5000010];
int S,T;
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int> > q;
q.push(make_pair(0,S));
dis[S]=0;
while(q.size()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(dis[v]>dis[u]+star[i].w){
dis[v]=dis[u]+star[i].w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
cin>>n>>p>>k;
cin>>S>>T;
++S;++T;
for(int i=1;i<=p;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
++u; ++v;
star[++cnt].add(u,v,w);
star[++cnt].add(v,u,w);
for(int j=0;j<k;j++){
star[++cnt].add((j+1)*n+u,(j+1)*n+v,w);
star[++cnt].add((j+1)*n+v,(j+1)*n+u,w);
star[++cnt].add(j*n+u,(j+1)*n+v,0);
star[++cnt].add(j*n+v,(j+1)*n+u,0);
}
}
for(int j=0;j<=k;j++){
star[++cnt].add(j*n+T,n*30+T,0);
}
dijkstra();
cout<<dis[n*30+T];
}
和上一道题思路一样，都是分层图，但连接第i层和第i+1层的边权不再是0，而是w/2；
#include <bits/stdc++.h>
using namespace std;
int head[5000010],cnt;
class littlestar{
public:
int to;
int nxt;
int w;
void add(int u,int v,int gg){
nxt=head[u];
to=v;
w=gg;
head[u]=cnt;
}
}star[5000010];
int n,p,k;
int dis[5000010],vis[5000010];
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int> > q;
q.push(make_pair(0,1));
dis[1]=0;
while(q.size()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(dis[v]>dis[u]+star[i].w){
dis[v]=dis[u]+star[i].w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
cin>>n>>p>>k;
for(int i=1;i<=p;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
star[++cnt].add(u,v,w);
star[++cnt].add(v,u,w);
for(int j=0;j<k;j++){
star[++cnt].add((j+1)*n+u,(j+1)*n+v,w);
star[++cnt].add((j+1)*n+v,(j+1)*n+u,w);
star[++cnt].add(j*n+u,(j+1)*n+v,w/2);
star[++cnt].add(j*n+v,(j+1)*n+u,w/2);
}
}
for(int j=0;j<=k;j++){
star[++cnt].add(j*n+n,n*30+1,0);
}
dijkstra();
cout<<dis[n*30+1];
}
4.[USACO09FEB]改造路Revamping Trails
思路重复，代码几乎一样，就不多说了；把这到题放到这里的原因是想告诉大家，USACO的题要好好做啊，很多省选题都来源于此；
#include <bits/stdc++.h>
using namespace std;
int head[5000010],cnt;
class littlestar{
public:
int to;
int nxt;
int w;
void add(int u,int v,int gg){
nxt=head[u];
to=v;
w=gg;
head[u]=cnt;
}
}star[5000010];
int n,p,k;
int dis[5000010],vis[5000010];
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int> > q;
q.push(make_pair(0,1));
dis[1]=0;
while(q.size()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(dis[v]>dis[u]+star[i].w){
dis[v]=dis[u]+star[i].w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
cin>>n>>p>>k;
for(int i=1;i<=p;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
star[++cnt].add(u,v,w);
star[++cnt].add(v,u,w);
for(int j=0;j<k;j++){
star[++cnt].add((j+1)*n+u,(j+1)*n+v,w);
star[++cnt].add((j+1)*n+v,(j+1)*n+u,w);
star[++cnt].add(j*n+u,(j+1)*n+v,0);
star[++cnt].add(j*n+v,(j+1)*n+u,0);
}
}
for(int j=0;j<=k;j++){
star[++cnt].add(j*n+n,n*30+1,0);
}
dijkstra();
cout<<dis[n*30+1];
}