记录编号	164125	评测结果	AAAAAAAAAA
题目名称	我们的铁骑	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.389 s
提交时间	2015-05-28 15:50:31	内存使用	10.40 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=100010;
vector<int> c_con[SIZEN];//邻接表
vector<pair<int,double> > cs[SIZEN];
vector<pair<int,double> > ct[SIZEN];
int n,m;
int s,t;
double fs[SIZEN]={0},ft[SIZEN]={0};
double L[SIZEN]={0},S[SIZEN]={0};
double att[SIZEN]={0};
void read(void){
	scanf("%d%d",&n,&m);
	s=1,t=n;
	int i;
	for(i=1;i<=n;i++) cin>>L[i];
	for(i=1;i<=n;i++) cin>>S[i];
	for(i=1;i<=n;i++) att[i]=min(L[i],S[i]);
	int a,b;
	for(i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		c_con[a].push_back(b);
		c_con[b].push_back(a);
	}
}
void makegraph_s(void){
	int i,j;
	double temp;
	for(i=1;i<=n;i++){
		for(j=0;j<c_con[i].size();j++){
			cs[i].push_back(make_pair(c_con[i][j],0));
		}
	}
	for(i=1;i<=n;i++){
		for(j=0;j<cs[i].size();j++){
			cs[i][j].second+=att[i]/2;
			cs[i][j].second+=att[cs[i][j].first]/2;
		}
	}
}
void makegraph_t(void){
	int i,j;
	double temp;
	for(i=1;i<=n;i++){
		for(j=0;j<c_con[i].size();j++){
			ct[i].push_back(make_pair(c_con[i][j],0));
		}
	}
	for(i=1;i<=n;i++){
		for(j=0;j<ct[i].size();j++){
			ct[i][j].second=S[ct[i][j].first]/2;
		}
	}
}
void Dijkstra_s(int s,double f[SIZEN]){
	double INF=1e18;
	priority_queue<pair<double,int> > q;
    bool l[SIZEN]={0};l[s]=1;
    fill_n(f,n+1,INF);f[s]=0;
    q.push(make_pair(-f[s],s));
	int i;
    while(!q.empty()){
        int u=q.top().second;q.pop();
        for(int i=0;i<cs[u].size();i++){
            int v=cs[u][i].first;
            if(f[v]>f[u]+cs[u][i].second){
                f[v]=f[u]+cs[u][i].second;
                if(!l[v]){
                    l[v]=1;
                    q.push(make_pair(-f[v],v));
                }
            }
        }
    }
	for(i=1;i<=n;i++){
		f[i]+=att[s]/2;
		f[i]+=att[i]/2;
	}
}
void Dijkstra_t(int s,double f[SIZEN]){
	double INF=1e18;
	priority_queue<pair<double,int> > q;
    bool l[SIZEN]={0};l[s]=1;
    fill_n(f,n+1,INF);f[s]=0;
    q.push(make_pair(-f[s],s));
	int i;
    while(!q.empty()){
        int u=q.top().second;q.pop();
        for(int i=0;i<ct[u].size();i++){
            int v=ct[u][i].first;
            if(f[v]>f[u]+ct[u][i].second){
                f[v]=f[u]+ct[u][i].second;
                if(!l[v]){
                    l[v]=1;
                    q.push(make_pair(-f[v],v));
                }
            }
        }
    }
	for(i=1;i<=n;i++){
		f[i]+=S[s];
		f[i]-=S[i]/2;
	}
}
void work(void){
	double ans=fs[n];
	int i;
	for(i=1;i<n;i++){
		if(fs[i]+ft[i]<ans){
			ans=fs[i]+ft[i];
		}
	}
	cout<<(long long)ans<<endl;
}
int main(){
	freopen("tank.in","r",stdin);
	freopen("tank.out","w",stdout);
	read();
	makegraph_s();
	makegraph_t();
	Dijkstra_s(s,fs);
	Dijkstra_t(t,ft);
	fs[n+1]=ft[n+1]=0;
	work();
	return 0;
}