乐乐与安安去古村落旅行。他们到达村口时，为了让旅途更有趣，约定同时出发，同时达到终点。已知村庄里有很多路标，两人约定只能从低路标走向高路标。两人从路标$1$（村口）出发，要到达路标n。 已知村庄里有 $n$ 个路标($1 \leq n \leq 100$)，$m$ 条路（$m \leq \dfrac{n\times(n-1)}{2}$），乐乐和安安走路速度是不同的，所以走每条路的时间也不同。现在，给出所有的路已经走每条路要花费的时间，请你求出乐乐与安安到达路标 $n$ 最少要花费多少时间。

输入格式

第一行包含两个整数 $n,m$。 接下来 $m$ 行，每行输入四个整数 $A,B,C,D$，表示路标 $A$ 和 $B$ 之间有一条路，$C$ 和 $D$ 分别表示乐乐和安安通过这条路需要花费的时间（$C$ 和 $D$ 都在 $1$ 到 $100$ 的范围内）。

输出格式

输出一个整数，表示最后的结果。如果问题无解，输出 IMPOSSIBLE。

样例

输入：

3 3
1 3 1 2
1 2 1 2
2 3 1 2

输出：

2

$50$ 分代码（SPFA）：

#include<bits/stdc++.h>
using namespace std;
int h[1005],val[100005],val2[100005],zd[100005],nxt[100005];
int dis[1005],dis2[1005],cnt=0;
int q[1000005],inq[1005];
int n,m;
void addedge(int a,int b,int c,int d){
    cnt++;
    val[cnt]=c,val2[cnt]=d,zd[cnt]=b,nxt[cnt]=0;
    nxt[cnt]=h[a];
    h[a]=cnt;
}
int main(){
    cin>>n>>m;
    for(register int i=1;i<=m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(a>b)swap(a,b);
        addedge(a,b,c,d);
    }
    memset(dis,-1,sizeof(dis));
    int f=1,e=1;
    q[1]=1,dis[1]=0,inq[1]=1;
    while(f<=e){
        int u=q[f++];
        for(int p=h[u];p;p=nxt[p]){
            int v=zd[p],c=val[p];
            if(dis[v]==-1||dis[v]>dis[u]+c){
                dis[v]=dis[u]+c;
                if(inq[v]==0){
                    q[++e]=v;
                    inq[v]=1;
                }
            }
        }
        inq[u]=0;
    }
    int ans1=dis[n];
    memset(dis2,-1,sizeof(dis));
    memset(inq,0,sizeof(inq));
    memset(q,0,sizeof(q));
    f=1,e=1;
    q[1]=1,dis2[1]=0,inq[1]=1;
    while(f<=e){
        int u=q[f++];
        for(int p=h[u];p;p=nxt[p]){
            int v=zd[p],c=val2[p];
            if(dis2[v]==-1||dis2[v]>dis2[u]+c){
                dis2[v]=dis2[u]+c;
                if(inq[v]==0){
                    q[++e]=v;
                    inq[v]=1;
                }
            }
        }
        inq[u]=0;
    }
    int ans2=dis2[n];
    if(ans1==-1||ans2==-1)cout<<"IMPOSSIBLE";
    else cout<<max(ans1,ans2);
}

$50$ 分代码（dijkstra）：

#include<bits/stdc++.h>
using namespace std;
int h[1005],val[100005],val2[100005],zd[100005],nxt[100005];
int dis[1005],dis2[1005],cnt=0;
int n,m;
int inq[10005];
void addedge(int a,int b,int c,int d){
    cnt++;
    val[cnt]=c,val2[cnt]=d,zd[cnt]=b,nxt[cnt]=0;
    nxt[cnt]=h[a];
    h[a]=cnt;
}
int main(){
    cin>>n>>m;
    for(register int i=1;i<=m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        addedge(a,b,c,d);
    }
    memset(dis,-1,sizeof(dis));
    int f=1,e=1;
    dis[1]=0;
    while(1){
        int q=-1,u=-1;
        for(register int i=1;i<=n;i++)if(!inq[i]&&dis[i]!=-1&&(q==-1||q>dis[i]))q=dis[i],u=i;
        if(q==-1)break;
        inq[u]=1;
        for(register int p=h[u];p;p=nxt[p]){
            int v=zd[p],c=val[p];
            if(inq[v]==0&&(dis[v]==-1||dis[v]>dis[u]+c))dis[v]=dis[u]+c; 
        }
    }
    int ans1=dis[n];
    memset(dis2,-1,sizeof(dis));
    memset(inq,0,sizeof(inq));
    f=1,e=1;
    dis2[1]=0;
    while(1){
        int q=-1,u=-1;
        for(register int i=1;i<=n;i++)if(!inq[i]&&dis2[i]!=-1&&(q==-1||q>dis2[i]))q=dis2[i],u=i;
        if(q==-1)break;
        inq[u]=1;
        for(register int p=h[u];p;p=nxt[p]){
            int v=zd[p],c=val2[p];
            if(inq[v]==0&&(dis2[v]==-1||dis2[v]>dis2[u]+c))dis2[v]=dis2[u]+c; 
        }
    }
    int ans2=dis2[n];
    if(ans1==-1&&ans2==-1)cout<<"IMPOSSIBLE";
    else cout<<max(ans1,ans2);
}

不知道错哪了，求调。