记录编号	586469	评测结果	AAAAAAAAAA
题目名称	[POJ 3255] 地砖RoadBlocks	最终得分	100
用户昵称	wow草原	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2024-01-26 20:31:40	内存使用	1.75 MiB

#include<bits/stdc++.h>
using namespace std;
int n,p,k,h[5010],maxx,tot,vis[5010],d1[5010],d2[5010],minx=1000001,m,sp[100010][4];
struct m{
    int ver,nx,ed;
}e[200010];
void add(int x,int y,int z){
    e[++tot].ver=y,e[tot].nx=h[x],e[tot].ed=z,h[x]=tot;
}
inline int read()
{
	int k=0,f=1;
    char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c&15);
	return k*f;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void spfa(int k1,int d[]){
       memset(vis,0,sizeof(vis));
        queue <int> a;
        a.push(k1),vis[k1]=1,d[k1]=0;
        while(!a.empty()){
            int x=a.front();
            a.pop();
            vis[x]=0;
            for(int i=h[x];i;i=e[i].nx){
                int y=e[i].ver;
                int z=e[i].ed;
                if(d[x]+z<d[y]){
                    
                    d[y]=d[x]+z;
                    if(!vis[y])vis[y]=1,a.push(y);
                }
            }
       }
}
int main(){
        freopen("block.in","r",stdin);
	freopen("block.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        x=read(),y=read(),z=read();
        add(x,y,z);
        add(y,x,z);
        sp[i][1]=x,sp[i][2]=y,sp[i][3]=z;
    }
    for(int i=1;i<=n;i++){
        d1[i]=minx;
        d2[i]=minx;
    }
    spfa(1,d1);
    spfa(n,d2);
    int ans=INT_MAX;
    for(int i=1;i<=m;i++){
        if(d1[sp[i][1]]+d2[sp[i][2]]+sp[i][3]<ans&&d1[sp[i][1]]+d2[sp[i][2]]+sp[i][3]!=d1[n]){
            ans=d1[sp[i][1]]+d2[sp[i][2]]+sp[i][3];
        }
        if(d1[sp[i][2]]+d2[sp[i][1]]+sp[i][3]<ans&&d1[sp[i][2]]+d2[sp[i][1]]+sp[i][3]!=d1[n]){
            ans=d1[sp[i][2]]+d2[sp[i][1]]+sp[i][3];
        }
    }
    cout<<ans;
    return 0;
}