bzoj 4398福慧双修題解
一晩中詰まったでしょう
まず、図全体のspfaを走りながら、各点がどの辺から出ているかを記録します(pre配列)
ここには前駆エッジではなく、原点につながる最初のポイント番号が記録されています.エッジを繰り返すことができないので、外に出たばかりで元の道に戻らないように記録します.
では、素朴な考え方があります.spfaが1点ずつつながっている点です.
実はこれでTになります...
ここから改善して、私たちは上の方法が多くの繰り返しの仕事を歩いていることを発見して、毎回spfaは実はとても似ています
新しい図を作ってspfaを走る過程を最適化することができます
この新しい図は、新しいポイントn+1を確立し、現在のエッジ(u,v,w)を設定する.
1.原点接続{
pre[v]!=vなら、1,v,wまで
そうでなければつながっていません
}
2.原点への{
pre[u]!=u直接dis[u]+wで答えを更新
さもないとu,n+1,w
}
3.その他、pre[u]=pre[v]が1からvまでdis[u]+wのエッジを構築する場合
そうでなければ元のエッジを保持
では、新しい図の最短ルートが答えです.
あるTが落ちた
まず、図全体のspfaを走りながら、各点がどの辺から出ているかを記録します(pre配列)
ここには前駆エッジではなく、原点につながる最初のポイント番号が記録されています.エッジを繰り返すことができないので、外に出たばかりで元の道に戻らないように記録します.
では、素朴な考え方があります.spfaが1点ずつつながっている点です.
実はこれでTになります...
ここから改善して、私たちは上の方法が多くの繰り返しの仕事を歩いていることを発見して、毎回spfaは実はとても似ています
新しい図を作ってspfaを走る過程を最適化することができます
この新しい図は、新しいポイントn+1を確立し、現在のエッジ(u,v,w)を設定する.
1.原点接続{
pre[v]!=vなら、1,v,wまで
そうでなければつながっていません
}
2.原点への{
pre[u]!=u直接dis[u]+wで答えを更新
さもないとu,n+1,w
}
3.その他、pre[u]=pre[v]が1からvまでdis[u]+wのエッジを構築する場合
そうでなければ元のエッジを保持
では、新しい図の最短ルートが答えです.
あるTが落ちた
//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#define o(e) ((((e)-1)^1)+1)
#define inc(a) a++;if(a==100000)a=1;
#define inf 1000000000
using namespace std;
inline void splay(int &v){
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
struct Edge{
int to,next,len;
}edge[200010];
int first[100010],size;
int dis[40010],dl[100010];
bool exsit[40010];
void addedge(int x,int y,int z){
size++;
edge[size].to=y;
edge[size].next=first[x];
first[x]=size;
edge[size].len=z;
}
int head,tail;
int spfa(int now,int lim){
head=0,tail=1;
memset(dis,63,sizeof dis);
dis[now]=0,dl[1]=now;
while(head!=tail){
inc(head);int v=dl[head];exsit[v]=false;
for(int u=first[v];u;u=edge[u].next){
if(edge[u].len+dis[v]<dis[edge[u].to] && u!=lim){
dis[edge[u].to]=edge[u].len+dis[v];
if(!exsit[edge[u].to]){
exsit[edge[u].to]=true;
inc(tail);dl[tail]=edge[u].to;
}
}
}
}
return dis[1];
}
int main(){
freopen("xxx.in","r",stdin);
freopen("xxx.out","w",stdout);
int n,m;splay(n),splay(m);
for(int i=1;i<=m;i++){
int s,e,l,r;
splay(s),splay(e),splay(l),splay(r);
addedge(s,e,l);addedge(e,s,r);
}
int ans=inf;
for(int u=first[1];u;u=edge[u].next){
ans=min(ans,spfa(edge[u].to,o(u))+edge[u].len);
}
cout<<ans<<endl;
}//Copyright(c)2015 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#define o(e) ((((e)-1)^1)+1)
#define inc(a) a++;if(a==100000)a=1;
#define inf 1000000000
using namespace std;
inline void splay(int &v){
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
struct Edge{
int to,next,len,from;
}edge[300010],e[300010];
int first[100010],size;
int dis[40010],dl[100010];
bool exsit[40010];
int pre[40010];
int f[40010],s;
int n,m;
void addedge(int x,int y,int z){
size++;
edge[size].to=y;
edge[size].next=first[x];
first[x]=size;
edge[size].len=z;
edge[size].from=x;
}
void add(int x,int y,int z){
s++;
e[s].to=y;
e[s].next=f[x];
f[x]=s;
e[s].len=z;
fprintf(stderr,"%d %d %d
",x,y,z);
}
int head,tail,ans=inf;
void spfa(){
while(head!=tail){
inc(head);int v=dl[head];exsit[v]=false;
for(int u=first[v];u;u=edge[u].next){
if(edge[u].len+dis[v]<dis[edge[u].to]){
dis[edge[u].to]=edge[u].len+dis[v];
pre[edge[u].to]=pre[v];
if(!exsit[edge[u].to]){
exsit[edge[u].to]=true;
inc(tail);dl[tail]=edge[u].to;
}
}
}
}
}
int Spfa(){
memset(dis,63,sizeof dis);
head=0,tail=1;dis[1]=0;dl[1]=1;
while(head!=tail){
inc(head);int v=dl[head];exsit[v]=false;
for(int u=f[v];u;u=e[u].next){
if(e[u].len+dis[v]<dis[e[u].to]){
dis[e[u].to]=e[u].len+dis[v];
if(!exsit[e[u].to]){
exsit[e[u].to]=true;
inc(tail);dl[tail]=e[u].to;
}
}
}
}
return dis[n+1];
}
int main(){
freopen("xxx.in","r",stdin);
freopen("xxx.out","w",stdout);
splay(n),splay(m);
for(int i=1;i<=m;i++){
int s,e,l,r;
splay(s),splay(e),splay(l),splay(r);
if(s==e&&s==1){
ans=min(ans,l),ans=min(ans,r);
}
else addedge(s,e,l),addedge(e,s,r);
}
memset(dis,63,sizeof dis);
for(int u=first[1];u;u=edge[u].next){
dl[++tail]=edge[u].to;
exsit[edge[u].to]=true;
pre[edge[u].to]=edge[u].to;
dis[edge[u].to]=edge[u].len;
}
spfa();
for(int i=1;i<=size;i++){
if(edge[i].to==1){
if(edge[i].from==pre[edge[i].from]){
add(edge[i].from,n+1,edge[i].len);
}
else{
ans=min(ans,dis[edge[i].from]+edge[i].len);
}
}
else if(edge[i].from==1){
if(pre[edge[i].to]!=edge[i].to){
add(1,edge[i].to,edge[i].len);
}
}
else{
if(pre[edge[i].from]==pre[edge[i].to]){
add(edge[i].from,edge[i].to,edge[i].len);
}
else{
add(1,edge[i].to,dis[edge[i].from]+edge[i].len);
}
}
}
cout<<Spfa()<<endl;
}