/ Vijos / 题库 / 最佳路线 /

题解

91 条题解

  • 4
    @ 2016-06-01 19:45:17 
    #include <cstdio>
#include <algorithm>
#include <algorithm>
using namespace std;
const int MAXN = 300;
const int INF = 1000000;

int dis[MAXN][MAXN], a[MAXN];

int main()
{
    int n, m, x, y, b;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
      scanf("%d", &a[i]);//第i个弯道时间
    for(int i=1; i<=n; i++)
      for(int j=i+1; j<=n; j++)
        dis[i][j] = dis[j][i] = INF;
    for(int i=1; i<=m; i++){
      scanf("%d%d%d", &x, &y, &b);
      dis[x][y] = min(dis[x][y], b); 
    }
    for(int k=1; k<=n; k++)
      for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
          dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j] + a[k]);
    int ans = INF;
    for(int i=2; i<=n; i++)
      ans = min(ans, dis[1][i] + a[i] + dis[i][1]);
    if(ans == INF)  printf("-1");
    else printf("%d", ans + a[1]);
    return 0;
}

    floyd = AC

  • 1
    @ 2019-02-11 14:23:25

    #include<cmath>
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int n,m,s[201],a[201][201];
    int main()
    {
    int i,j,k,x,y,b;
    scanf("%d%d",&n,&m);
    memset(a,0x3f,sizeof(a));
    for(i=1;i<=n;i++)
    scanf("%d",&s[i]);
    for(i=1;i<=m;i++)
    {
    scanf("%d%d%d",&x,&y,&b);
    if(b+s[y]<a[x][y])
    a[x][y]=b+s[y];
    }
    for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
    if(a[i][j]>a[i][k]+a[k][j])
    {
    a[i][j]=a[i][k]+a[k][j];
    }
    }
    if(a[1][1]==0x3f3f3f3f)
    printf("-1");
    else
    printf("%d",a[1][1]);
    return 0;
    }

  • 1
    @ 2018-07-15 21:13:36 
    //vijos p1423 最佳路线
//就是求经过点一的最小环(不过有点权)有向图 
//时间复杂度最坏n^2*logn n=200
#include<bits/stdc++.h> 
#define re register int
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
template<class T>inline bool sdf(T&x){
    char c;register int y=1;while(c=getchar(),c<48||57<c)if(c=='-')y=-1;x=c^48;
    while(c=getchar(),47<c&&c<58)x=(x<<1)+(x<<3)+(c^48);x*=y;
    return true;
}
const int maxn=201; 
int d[maxn];
int g[maxn][maxn];
bool vis[maxn];
int inf;
int n,m;
typedef pair<int,int> P;
int dijkstra(int start){
    priority_queue <P,vector<P>,greater<P> > que;
    memset(d,0x3f,sizeof(d));
    d[start]=0; 
    que.push(P(0,start));
    bool flag=0;
    while(!que.empty()){
        re u=que.top().second;
        que.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=1;i<=n;i++){
            if(i!=u){
            if(d[i]>d[u]+g[u][i]+g[i][i]){
                d[i]=d[u]+g[u][i]+g[i][i];
                que.push(P(d[i],i));
            }
            }
        }
        if(!flag){
            flag=1;
            d[start]=inf;
            vis[start]=0;
        }
    }
    return d[start];
} 
int main(){
    sdf(n),sdf(m);
    int x,y,z;
    memset(g,0x3f,sizeof(g));
    inf=g[0][0];
    for(re i=1;i<=n;i++) sdf(g[i][i]);
    for(re i=1;i<=m;i++) 
    {
        sdf(x),sdf(y),sdf(z);
        g[x][y]=min(g[x][y],z);
    }
    int ans=dijkstra(1);
    if(ans==inf) puts("-1");
    else printf("%d",ans);
}
    • @ 2018-07-15 21:15:37

      跑得飞快
      #1 Accepted 2ms 504.0 KiB
      #2 Accepted 2ms 500.0 KiB
      #3 Accepted 3ms 408.0 KiB
      #4 Accepted 2ms 500.0 KiB
      #5 Accepted 3ms 512.0 KiB
      #6 Accepted 2ms 496.0 KiB
      #7 Accepted 11ms 512.0 KiB
      #8 Accepted 3ms 492.0 KiB
      #9 Accepted 5ms 484.0 KiB
      #10 Accepted 16ms 512.0 KiB

  • 0
    @ 2019-02-11 14:22:45

    #include<cmath>
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int n,m,s[201],a[201][201];
    int main()
    {
    int i,j,k,x,y,b;
    scanf("%d%d",&n,&m);
    memset(a,0x3f,sizeof(a));
    for(i=1;i<=n;i++)
    scanf("%d",&s[i]);
    for(i=1;i<=m;i++)
    {
    scanf("%d%d%d",&x,&y,&b);
    if(b+s[y]<a[x][y])
    a[x][y]=b+s[y];
    }
    for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
    if(a[i][j]>a[i][k]+a[k][j])
    {
    a[i][j]=a[i][k]+a[k][j];
    }
    }
    if(a[1][1]==0x3f3f3f3f)
    printf("-1");
    else
    printf("%d",a[1][1]);
    return 0;
    }

  • 0
    @ 2016-12-28 21:45:20

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 752 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 752 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 752 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 752 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 752 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 752 KiB, score = 10
    测试数据 #6: Accepted, time = 109 ms, mem = 756 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 756 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 752 KiB, score = 10
    测试数据 #9: Accepted, time = 109 ms, mem = 752 KiB, score = 10
    Accepted, time = 248 ms, mem = 756 KiB, score = 100

    先用floyd过一次再想想怎么用dijkstra。。。

    代码
    ```c++
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<vector>
    #include<sstream>
    #include<algorithm>
    #include<string>
    #include<cstdio>
    #include<math.h>
    #include<map>
    #include<cctype>
    #include<queue>
    #include<functional>
    #include<set>
    #define Mem(a,b) memset((a),(b),sizeof((a)))
    #define Sy system("pause")
    #define For(a,b) for(int i = (a);i<(b);i+=1)
    const int maxn = 220;
    const int INF = 0x3f3f3f;
    using namespace std;
    int d[maxn], G[maxn][maxn];
    int ans = INF;
    int main(){
    For(0, maxn){
    d[i] = INF;
    for (int j = 0; j < maxn; j += 1) G[i][j] = i == j ? 0 : INF;
    }
    int n, m, a, b, c;
    scanf("%d %d", &n, &m);
    For(1, n + 1) scanf("%d", &d[i]);
    For(1, m + 1){
    scanf("%d %d %d", &a, &b, &c);
    G[a][b] = min(G[a][b], c);
    }

    for (int k = 1; k <= n; k += 1)
    for (int i = 1; i <= n; i += 1)
    for (int j = 1; j <= n; j += 1){
    G[i][j] = min(G[i][j], G[i][k] + G[k][j] + d[k]);
    }

    For(2, n + 1){
    ans = min(ans, G[1][i] + G[i][1] + d[i]);
    }
    if (ans != INF)
    printf("%d\n", ans + d[1]);
    else
    printf("-1\n");
    //Sy;
    return 0;
    }
    ```

  • 0
    @ 2016-08-25 07:53:53

    SPFA
    #include"iostream"

    #include"cstring"

    #include"math.h"
    #include"cstdio"
    #include"map"
    #include"set"
    #include"algorithm"
    #include"vector"
    #include"queue"

    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    const int INF=110000000; //最大边数*最大边长+10
    const int maxn=200+10;//最大点数
    int a[maxn];
    struct edge //边
    {
    int from,to,dist;edge(int u,int v,int w){from=u;to=v;dist=w;}
    };
    struct node
    {
    int d;int u;
    node(){}
    node(int dd,int uu){d=dd;u=uu;}
    friend bool operator < (node a,node b){return a.d>b.d;}
    };
    struct dijkstra
    {

    int n,m;
    vector<edge>edges;
    vector<int>g[maxn];

    int visit[maxn]; //dijkstra

    int cnt[maxn]; //SPFA
    int inq[maxn];

    int d[maxn];
    int p[maxn];

    void init(int n){this->n=n;for(int i=0;i<n;i++)g[i].clear();edges.clear();}
    void add_edge(int u,int v,int w){edges.push_back(edge(u,v,w));int m=edges.size();g[u].push_back(m-1);} //加入一条边 无向图要加两次

    void djk(int s)
    {
    priority_queue<pii,vector<pii>,greater<pii> >Q;
    memset(visit,0,sizeof(visit));
    for(int i=0;i<n;i++) d[i]=INF;
    d[s]=a[s];
    Q.push(make_pair(d[s],s));
    while(!Q.empty())
    {
    pii x=Q.top();Q.pop();
    int u=x.second;
    visit[u]=1;
    for(int i=0;i<g[u].size();i++)
    {
    edge& e=edges[g[u][i]];
    if(!visit[e.to])
    if(d[e.to]>d[e.from]+e.dist+a[e.to])
    {
    d[e.to]=d[e.from]+e.dist+a[e.to];
    p[e.to]=g[u][i];
    Q.push(make_pair(d[e.to],e.to));
    }
    }
    }

    }
    int SPFA(int s)
    {
    queue<int>Q;
    memset(inq,0,sizeof(inq));
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<n;i++) d[i]=INF;
    d[s]=a[s];
    Q.push(s);
    inq[s]=1;cnt[s]=1;
    while(!Q.empty())
    {
    int u=Q.front();Q.pop();
    inq[u]=0;
    for(int i=0;i<g[u].size();i++)
    {
    edge &e=edges[g[u][i]];

    if(d[e.from]<INF&&d[e.to]>d[e.from]+e.dist+a[e.to]) //松弛
    {
    d[e.to]=d[e.from]+e.dist+a[e.to];

    if(!inq[e.to]) //不在队列中才能入队
    {
    Q.push(e.to);
    inq[e.to]=1;cnt[e.to]++;
    if(cnt[e.to]>n) return 0;
    }
    }
    }
    }
    return 1;
    }
    };

    int main()
    {

    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
    int i,j,k;
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    dijkstra b,c;
    b.init(n);c.init(n);
    for(i=1;i<=m;i++)
    {
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    b.add_edge(u-1,v-1,w);c.add_edge(u-1,v-1,w);
    }
    int Min=INF;
    b.SPFA(0);
    for(i=1;i<n;i++)
    {
    c.SPFA(i);
    Min=min(b.d[i]+c.d[0]-a[0]-a[i],Min);
    }
    if(Min==INF) puts("-1");
    else printf("%d\n",Min);

    }
    return 0;
    }

  • 0
    @ 2016-08-25 07:25:34

    楼下说的正反遍历我没实现成功，但是正向遍历一遍然后枚举另一个点是可以的。
    Dijkstra
    #include"iostream"
    #include"cstring"
    #include"math.h"
    #include"cstdio"
    #include"map"
    #include"set"
    #include"algorithm"
    #include"vector"
    #include"queue"

    using namespace std;
    typedef long long ll;
    typedef pair<int,int> pii;
    const int INF=110000000; //最大边数*最大边长+10
    const int maxn=200+10;//最大点数
    int a[maxn];
    struct edge //边
    {
    int from,to,dist;edge(int u,int v,int w){from=u;to=v;dist=w;}
    };
    struct node
    {
    int d;int u;
    node(){}
    node(int dd,int uu){d=dd;u=uu;}
    friend bool operator < (node a,node b){return a.d>b.d;}
    };
    struct dijkstra
    {

    int n,m;
    vector<edge>edges;
    vector<int>g[maxn];
    int visit[maxn];
    int d[maxn];
    int p[maxn];

    void init(int n){this->n=n;for(int i=0;i<n;i++)g[i].clear();edges.clear();}
    void add_edge(int u,int v,int w){edges.push_back(edge(u,v,w));int m=edges.size();g[u].push_back(m-1);} //加入一条边 无向图要加两次

    void djk(int s)
    {
    priority_queue<pii,vector<pii>,greater<pii> >Q;
    memset(visit,0,sizeof(visit));
    for(int i=0;i<n;i++) d[i]=INF;
    d[s]=a[s];
    Q.push(make_pair(d[s],s));
    while(!Q.empty())
    {
    pii x=Q.top();Q.pop();
    int u=x.second;
    visit[u]=1;
    for(int i=0;i<g[u].size();i++)
    {
    edge& e=edges[g[u][i]];
    if(!visit[e.to])
    if(d[e.to]>d[e.from]+e.dist+a[e.to])
    {
    d[e.to]=d[e.from]+e.dist+a[e.to];
    p[e.to]=g[u][i];
    Q.push(make_pair(d[e.to],e.to));
    }
    }
    }

    }

    };

    int main()
    {

    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
    int i,j,k;
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    dijkstra b,c;
    b.init(n);c.init(n);
    for(i=1;i<=m;i++)
    {
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    b.add_edge(u-1,v-1,w);c.add_edge(u-1,v-1,w);
    }
    int Min=INF;
    b.djk(0);
    for(i=1;i<n;i++)
    {
    c.djk(i);
    Min=min(b.d[i]+c.d[0]-a[0]-a[i],Min);
    }

    /*
    int Min=INF;
    for(i=1;i<n;i++)
    {
    b.djk(0);c.djk(i);
    Min=min(Min,b.d[i]+c.d[0]-a[i]-a[0]);
    }
    */
    if(Min==INF) puts("-1");
    else printf("%d\n",Min);

    }
    return 0;
    }

  • 0
    @ 2016-08-14 11:30:53

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 720 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 720 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 720 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 720 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 724 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 720 KiB, score = 10
    测试数据 #6: Accepted, time = 375 ms, mem = 720 KiB, score = 10
    测试数据 #7: Accepted, time = 46 ms, mem = 716 KiB, score = 10
    测试数据 #8: Accepted, time = 46 ms, mem = 720 KiB, score = 10
    测试数据 #9: Accepted, time = 312 ms, mem = 724 KiB, score = 10
    Accepted, time = 809 ms, mem = 724 KiB, score = 100

    /*
    引用楼下wang...yanheng大神的话：
    对于此题而言，floyd可以做，但不是最优选择。如果把数据加强到n=1000，
    则应该使用两次Dijkstra（正向反向各一次），然后枚举中间点来选取答案。
    这样做的时间复杂度为O(V2)O(V2)，对于n=1000绰绰有余。

    Floyd做法：a[i]表示第i个弯道时间，d[i][j]表示第i个弯道到第j个弯道时间，初始化INF
    接着运用floyd求出各个弯道之间直道最短时间，记得要加上连接弯道的直道时间。
    题目要求要经过1弯道的最短路且必要有一直道路，说明必要有两个弯道连接而成加上直道，
    则枚举2到n所有点，取其d[1][i]+a[i]+d[i][1]+a[1]最小值。
    还需要判断是否存在解即判断与INF的关系。
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;

    const int INF=0x7ffffff;
    int d[202][202];
    int a[202];
    int n,m;

    int main()
    {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(i!=j) d[i][j]=INF;
    for(int i=1;i<=m;i++)
    {
    int x,y,v;
    cin>>x>>y>>v;
    d[x][y]=min(d[x][y],v);
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    d[i][j]=min(d[i][j],d[i][k]+a[k]+d[k][j]);
    int ans=INF;
    for(int i=2;i<=n;i++)
    ans=min(ans,d[1][i]+a[i]+d[i][1]+a[1]);
    if(ans==INF)
    cout<<"-1"<<endl;
    else
    cout<<ans<<endl;
    return 0;
    }

  • 0
    @ 2016-07-29 21:02:32

    对于此题而言，floyd可以做，但不是最优选择。如果把数据加强到n=1000，则应该使用两次Dijkstra（正向反向各一次），然后枚举中间点来选取答案。这样做的时间复杂度为\(O(V^2)\)，对于n=1000绰绰有余。

  • 0
    @ 2016-01-30 19:20:24

    求第6组数据！！！

  • 0
    @ 2015-08-04 19:24:52

    program p1423;
    var a:array[1..200,1..200] of longint;
    w:array[1..200] of longint;
    i,j,k,l,m,n,r,q,p:longint;
    begin
    readln(n,m);
    for i:=1 to n do
    for j:=1 to n do a[i,j]:=10000000;
    for i:=1 to n do readln(w[i]);
    for i:=1 to m do
    begin readln(p,q,r);
    if r+w[q]<a[p,q] then a[p,q]:=r+w[q];
    end;
    for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
    if a[i,j]>a[i,k]+a[k,j] then
    a[i,j]:=a[i,k]+a[k,j];
    if a[1,1]=10000000 then a[1,1]:=-1;
    writeln(a[1,1]);
    end.

  • 0
    @ 2015-07-07 00:53:42

    P1423最佳路线
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1423 最佳路线
    递交时间 2015-07-07 00:53:14
    代码语言 C++
    评测机 VijosEx
    消耗时间 294 ms
    消耗内存 440 KiB
    评测时间 2015-07-07 00:53:17

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 436 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 440 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 436 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 440 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 440 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 436 KiB, score = 10

    测试数据 #6: Accepted, time = 109 ms, mem = 436 KiB, score = 10

    测试数据 #7: Accepted, time = 15 ms, mem = 440 KiB, score = 10

    测试数据 #8: Accepted, time = 46 ms, mem = 436 KiB, score = 10

    测试数据 #9: Accepted, time = 109 ms, mem = 436 KiB, score = 10

    Accepted, time = 294 ms, mem = 440 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>

    using namespace std;

    int n , m;
    int i , j , k;
    int a[200 + 2];
    int g[200 + 2][200 + 2];
    int x , y , w;
    int mind;

    int min( int a , int b )
    {
    if( a > b )
    return b;
    return a;
    }

    int main()
    {
    scanf( "%d %d" , &n , &m );
    for( i = 1 ; i <= n ; i++ )
    scanf( "%d" , &a[i] );
    for( i = 1 ; i <= n ; i++ )
    for( j = 1 ; j <= n ; j++ )
    g[i][j] = 10000000;
    for( i = 1 ; i <= n ; i++ )
    g[i][i] = 0;
    for( i = 0 ; i < m ; i++ )
    {
    scanf( "%d %d %d" , &x , &y , &w );
    g[x][y] = min( g[x][y] , w );
    }
    for( k = 1 ; k <= n ; k++ )
    for( i = 1 ; i <= n ; i++ )
    for( j = 1 ; j <= n ; j++ )
    g[i][j] = min( g[i][j] , g[i][k] + g[k][j] + a[k] );
    int mind = 10000000;
    for( k = 2 ; k <= n ; k++ )
    mind = min( mind , g[1][k] + g[k][1] + a[k] + a[1] );
    if( mind != 10000000 )
    cout << mind << endl;
    else
    cout << -1 << endl;
    return 0;
    }

  • 0
    @ 2015-05-20 15:53:04

    SO EASy！！！
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<cstring>
    using namespace std;
    int w[201][201],a[201],f[201];
    queue <int>que;
    int n,m;
    int main()
    {
    int x,y,z,ans=5555555;
    //freopen("P1423.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
    scanf("%d%d%d",&x,&y,&z);
    if(w[x][y]==0||w[x][y]>z)
    w[x][y]=z;
    }
    memset(f,100,sizeof(f));
    que.push(1);
    f[1]=0;
    int k;
    while(que.size()!=0)
    {
    k=que.front();
    que.pop();
    for(int i=1;i<=n;i++)
    if(w[k][i]>0&&(f[i]>f[k]+w[k][i]+a[i]||f[i]==0))
    {
    f[i]=f[k]+w[k][i]+a[i];
    if(i==1&&(ans==0||ans>f[i]))
    ans=f[i];
    else
    que.push(i);
    }
    }
    if(ans==5555555)
    {
    printf("-1");
    return 0;
    }
    printf("%d",ans);
    return 0;

    }

  • 0
    @ 2014-03-29 09:05:47

    var dist,time:array[0..201] of longint;
    map:array[0..201,0..201] of longint;
    i,ans,n,m,j,a,b,c:longint;
    function min(x,y:longint):longint;
    begin
    if x<y then exit(x) else exit(y);
    end;
    procedure spfa;
    var h,t,x:longint;
    vis:array[0..201] of boolean;
    q:array[0..201] of longint;
    begin
    fillchar(vis,sizeof(vis),false);
    fillchar(q,sizeof(q),0);
    h:=0;t:=1;q[1]:=1;vis[1]:=true;dist[1]:=time[1];
    while h<>t do
    begin
    h:=h mod n+1;
    x:=q[h];
    vis[x]:=false;
    for i:=1 to n do
    if (map[x,i]<>maxlongint shr 1) and (dist[x]+map[x,i]+time[i]<dist[i]) then
    begin
    dist[i]:=dist[x]+map[x,i]+time[i];
    if not(vis[i]) then
    begin
    t:=t mod n+1;
    q[t]:=i;
    vis[i]:=true;
    end;
    end;
    end;
    end;
    begin
    readln(n,m);
    for i:=1 to n do
    for j:=1 to n do
    map[i,j]:=maxlongint shr 1;
    for i:=1 to n do readln(time[i]);
    for i:=1 to m do
    begin
    readln(a,b,c);
    map[a,b]:=min(map[a,b],c);
    end;
    for i:=1 to n do dist[i]:=maxlongint shr 1;
    spfa;
    ans:=maxlongint;
    for i:=2 to n do ans:=min(ans,dist[i]+map[i,1]);
    if ans>maxlongint shr 1 then writeln('-1') else writeln(ans);
    end.
    直接SPFA！

  • 0
    @ 2013-09-30 19:18:43

    对这个测评机彻底无语，0秒超时，0.2秒反而ac

  • 0
    @ 2012-09-27 20:47:18

    各位大牛，帮忙看看这个怎么只能过9个点，最后一个过不了

    const maxn=100000000;

    var w:array[1..200] of longint;

    q,d:array[1..200] of longint;

    mark:array[1..200] of boolean;

    a,b:array[1..200,0..200] of longint;

    n,m,x,y,z,min:longint;

    i,j,h,t,p:longint;

    begin

    fillchar(w,sizeof(w),0);

    fillchar(b,sizeof(b),0);

    fillchar(a,sizeof(a),0);

    readln(n,m);

    for i:=1 to n do

    readln(w[i]);

    for i:=1 to m do

    begin

    readln(x,y,z);

    if a[x,y]>0 then

    if z+w[y]0 then

    begin

    inc(b);

    b[i,b]:=j;

    end;

    fillchar(q,sizeof(q),0);

    fillchar(mark,sizeof(mark),false);

    for i:=2 to n do

    d[i]:=maxn;

    h:=0;

    t:=1;

    q[1]:=1;

    mark[1]:=true;

    d[1]:=0;

    while ht do

    begin

    h:=(h mod n)+1;

    p:=h;

    mark[p]:=false;

    for i:=1 to b[p,0] do

    if d[p]+a[p,b[p,i]]

  • 0
    @ 2012-09-24 20:01:34

    ├ 测试数据 01：答案正确... (0ms, 1216KB)

    ├ 测试数据 02：答案正确... (0ms, 1216KB)

    ├ 测试数据 03：答案正确... (0ms, 1216KB)

    ├ 测试数据 04：答案正确... (0ms, 1216KB)

    ├ 测试数据 05：答案正确... (0ms, 1216KB)

    ├ 测试数据 06：答案正确... (0ms, 1216KB)

    ├ 测试数据 07：答案正确... (0ms, 1216KB)

    ├ 测试数据 08：答案正确... (0ms, 1216KB)

    ├ 测试数据 09：答案正确... (0ms, 1216KB)

    ├ 测试数据 10：答案正确... (0ms, 1216KB)

    每个弯道拆成两个点，然后spfa

  • 0
    @ 2009-11-07 09:54:44

    。。跳楼算了。这种水题交了5遍。

    看到那爆小的数据范围，有种想用Floyd的冲动。

    但抱着对Spfa的热爱，用了Spfa。

    看到那爆小的数据范围，心血来潮，把使用多年的邻接表改成邻接矩阵。

    结果。重边的判断错了N次.杯具啊。。。

    （邻接表是不用判重边的I.I）

  • 0
    @ 2009-11-03 21:39:44

    Accepted 有效得分：100 有效耗时：0ms

    把读入的右边的1当成n+1,求1-n+1的最短路就行了额..注意重边哦~~

  • 0
    @ 2009-10-31 01:16:57

    30分/80分的同志们注意下。。fillchar(127)是会挂的。。建议改成for。。g初始=10^7刚好。。

最佳路线

信息

ID
1423
难度
5
分类
图结构 | 最短路 点击显示
标签
递交数
1849
已通过
586
通过率
32%
被复制
2
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1