题解

88 条题解

  • 2
    @ 2019-09-12 15:56:30

    Dijkstra
    记录每次选中点的上一个路径源,从终点向前遍历,找到路径。

    #include <iostream>
    #include <cstring>
    #include <vector>
    
    using namespace std;
    
    int n;
    int ma[1001][1001]={0};
    
    int dis[1001];
    int last[1001]={0};
    bool vis[1001]={0};
    
    int main()
    {
        cin>>n;
        int i,j,ans,now,next;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                cin>>ma[i][j];
            }
        }
        vis[1]=true;
        memset(dis,62,sizeof(dis));
        dis[1]=0;
        now=1;
        while(now!=n)
        {
            ans=1e9;
            for(i=1;i<=n;i++)
            {
                if(ma[now][i]>0&&!vis[i])
                {
                    if(dis[i]>dis[now]+ma[now][i])
                    {
                        dis[i]=dis[now]+ma[now][i];
                        last[i]=now;
                    }
                }
                if(ans>dis[i]&&!vis[i])
                {
                    ans=dis[i];
                    next=i;
                }
            }
            vis[next]=true;
            now=next;
        }
        vector<int> vi;
        now=n;
        vi.push_back(now);
        while(now!=1)
        {
            now=last[now];
            vi.push_back(now);
        }
        for(i=vi.size()-1;i>=0;i--)
        {
            cout<<vi[i]<<' ';
        }
        cout<<endl;
        cout<<ans<<endl;
        return 0;
    }
    
  • 0
    @ 2019-04-18 10:03:20

    #include <iostream>
    using namespace std;
    #include <stack>
    #define INFT 0x232323
    #define WHITE 0
    #define BLACK 1
    #define GRAY -1

    int visited[10001];
    int G[10001][10001];
    int parent[10001];
    int d[10001];
    int N;

    void initial()
    {
    for (int i = 0; i < 10001; i++)
    {
    d[i] = INFT;
    parent[i] = -1;
    visited[i] = 0;
    }

    }

    void Djkar(int s, int e)
    {
    d[s] = 0;

    while (1)
    {
    int minv = INFT;
    int choice = -1;

    for (int i = 1; i <= N; i++)
    {
    if (visited[i] != BLACK && d[i] < minv)
    {
    minv = d[i];
    choice = i;
    }
    }

    if (choice == -1)
    break;

    visited[choice] = BLACK;

    for (int i = 1; i <= N; i++)
    {
    if (visited[i] != BLACK && G[choice][i] != INFT)
    {
    if (G[choice][i] + d[choice] < d[i])
    {
    d[i] = G[choice][i] + d[choice];
    parent[i] = choice;
    visited[i] = GRAY;
    }
    }
    }
    }
    stack<int> ss;

    int po = e;

    ss.push(po);

    while (parent[po] != -1)
    {
    ss.push(parent[po]);
    po = parent[po];
    }

    cout << ss.top();
    ss.pop();

    while (!ss.empty())
    {
    cout << " " << ss.top();
    ss.pop();
    }
    cout << endl;
    cout << d[e];
    }

    int main()
    {
    cin >> N;
    initial();

    for(int i=1;i<=N;i++)
    for (int j = 1; j <= N; j++)
    {
    int tmp;
    cin >> tmp;
    if (tmp)
    {
    G[i][j] = tmp;
    }
    else
    {
    G[i][j] = INFT;
    }
    }

    Djkar(1, N);
    r****

  • 0
    @ 2018-02-08 09:56:55

    迪杰特斯拉嘻嘻 记录路线的有一点点麻烦(也许是我太菜)
    ```cpp
    #include<stdio.h>
    const int maxn=110,INF=1<<29;
    long long int mp[1100][1100],dis[1100],v[1100],lu[1100];
    int main() {
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
    for(int j=1; j<=n; j++) {
    scanf("%d",&mp[i][j]);
    if(!mp[i][j])mp[i][j]=INF;
    }
    }
    for(int i=1; i<=n; i++) {
    dis[i]=mp[1][i];
    }
    v[1]=1;
    int k=0;
    for(int i=1;i<=n;i++)lu[i]=1;
    int flag=1;
    for(int i=1; i<=n; i++) {
    int minn=INF;
    int p;
    for(int j=1; j<=n; j++) {
    if(!v[j]&&dis[j]<minn) {
    minn=dis[j];
    p=j;
    }
    }
    v[p]=1;
    if(flag){
    lu[p]=1;//经过第一个p的最短路是来自起点1的
    flag=0;
    }
    for(int j=1; j<=n; j++) {
    if(dis[p]+mp[p][j]<dis[j]) {
    dis[j]=dis[p]+mp[p][j];
    lu[j]=p;//到j点的最短路是来自于p的 ->到终点的最短路是来自于上一个p的
    }
    }

    }
    int swap[1100]={0};
    k=0;
    for (int i=n;i>1;i=lu[i]) swap[k++]=lu[i];//lu数组中记录的是倒着的 而且不包含终点 所以交换一下
    for(int i=k-1;i>=0;i--)printf("%d ",swap[i]);
    printf("%d\n",n);
    printf("%d\n",dis[n]);
    }
    ```

  • 0
    @ 2017-11-06 16:52:51

    dijkstra来一波
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int M=10000000;
    int n,m,p,t;
    int g[1008][1008],pre[1008],c[1008],pree[1008];
    bool b[1008];
    void dijkstra()
    {
    for(int i=1;i<=n;i++)
    {
    int minl=M,k=0;
    for(int j=1;j<=n;j++)
    if(!b[j]&&minl>c[j])
    {
    minl=c[j];
    k=j;
    }
    if(k==0) break;
    b[k]=true;
    for(int j=1;j<=n;j++)
    if(c[k]+g[k][j]<c[j])
    {
    pre[j]=k;
    c[j]=c[k]+g[k][j];
    }
    }
    return;
    }
    void outans(int a)
    {
    if(a==1) return;
    outans(pre[a]);
    cout<<" "<<a;
    }
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
    cin>>g[i][j];
    if(g[i][j]==0) g[i][j]=M;
    }
    for(int i=1;i<=n;i++)
    {c[i]=g[1][i]; pre[i]=1;}
    b[1]=true; c[1]=0;
    dijkstra();
    cout<<1;
    outans(n);
    cout<<endl<<c[n];
    return 0;
    }

  • 0
    @ 2017-10-26 20:57:18

    来个Dijkstra

    #include<algorithm>
    #include <iostream>
    #include  <cstring>
    #include   <cstdio>
    #include    <cmath>
    using namespace std;
    const int MAXN = 1001;
    const int INF  = 99999999;
    #define For(i, a, b) for(int i=a; i<=b; i++)
    #define Dow(i, a, b) for(int i=a; i>=b; i--)
    
    void Read(int&);
    
    int n, map[MAXN][MAXN];
    int dis[MAXN], pre[MAXN];
    bool vis[MAXN];
    
    inline void init() {
        Read(n);
        For(i, 1, n) For(j, 1, n) {
            scanf("%d", &map[i][j]);
            if(!map[i][j]) map[i][j] = INF;
        }
    }
    
    inline void Dijkstra(int s) {
        memset(vis, false, sizeof(vis));
        vis[s] = true;
        For(i, 1, n) {
            dis[i] = map[s][i];
            pre[i] = s;
        }
        int Min_val, Min_pos;
        For(i, 2, n) {
            Min_val = INF;
            For(j, 1, n)
                if(!vis[j] && dis[j]<Min_val) {
                    Min_val = dis[j];
                    Min_pos = j;
                }
            vis[Min_pos] = true;
            For(j, 1, n) {
                if(!vis[j] && map[Min_pos][j]+Min_val<dis[j]) {
                    dis[j] = map[Min_pos][j]+Min_val;
                    pre[j] = Min_pos; 
                }
            }
        }
    }
    
    void print(int x) {
        if(x == 1) return ;
        print(pre[x]);
        printf("%d ", x);
    }
    
    int main() {
        
        init();
        Dijkstra(1);
        printf("%d ", 1); print(n);
        printf("\n%d", dis[n]);
        
        return 0;
    }
    
    inline void Read(int &x) {
        bool fg=1; char ch;
        ch = getchar();
        if(ch == '-') { fg=-1; printf("-"); ch = getchar(); }
        while(ch>='0' && ch<='9') {
            x = (x<<3) + (x<<1) + ch - 48;
            ch = getchar();
        }
        x *= fg;
    }
    
    
    
  • 0
    @ 2017-10-02 00:30:34
    var
      a,w:array[-1..10000,-1..10000] of longint;
      p,d,pre:array[-1..10000] of longint;
      f:array[-1..10000] of boolean;
      i,j,n,xx,yy,t,tt:longint;
    
    procedure spfa(v:longint);
    var
      i,x:longint;
    begin
      fillchar(d,sizeof(d),$7f);
      fillchar(f,sizeof(f),false);
      d[v]:=0; t:=0; tt:=1; p[1]:=v; f[v]:=true;
      while t<=tt do
      begin
        t:=t+1;
        x:=p[t];
        f[x]:=false;
        for i:=1 to a[x,-1] do
          if d[a[x,i]]>d[x]+w[x,a[x,i]] then
          begin
            d[a[x,i]]:=d[x]+w[x,a[x,i]];
            pre[a[x,i]]:=x;
            if not(f[a[x,i]]) then
            begin tt:=tt+1; p[tt]:=a[x,i]; f[a[x,i]]:=true; end;
          end;
      end;
    end;
    
    procedure pp(v:longint);
    begin
      if v=1 then write(v,' ')
      else
      begin
        pp(pre[v]);
        write(v,' ');
      end;
    end;
    
    begin
      readln(n);
      for i:=1 to n do
      for j:=1 to n do
      begin
        read(w[i,j]);
        if w[i,j]>0 then
          begin
            inc(a[i,-1]);
            a[i,a[i,-1]]:=j;
          end;
      end;
      spfa(1);
      pp(n);
      writeln;
      write(d[n]);
    end.
    
  • 0
    @ 2017-08-04 20:41:05

    Pascal版SPFA

    const INF=maxlongint div 3;
    type
        rel=array[0..100001] of longint;
    var
        a:array[1..1001,1..1001] of longint;
        way:rel;
        i,j,n,m,x,y,p,q,c,ans:longint;
    
    function exist(w:rel; l,r,x:longint):boolean;
    var i:longint;
    begin
        for i:=l to r-1 do
            if w[i]=x then exit(true);
        exit(false);
    end;
    
    function spfa(x,y:longint):longint;
    var
        dis,pre,v:rel;
        i,j,l,r:longint;
    begin
    
    //spfa
    
        fillchar(v,sizeof(v),0);
        for i:=1 to n do dis[i]:=INF; dis[x]:=0;
        l:=1; r:=2; v[1]:=x;
        while l<r do begin
            for i:=1 to n do
                if (a[v[l],i]<>INF) and (a[v[l],i]<>0) then
                    if dis[v[l]]+a[v[l],i]<dis[i] then begin
                        dis[i]:=dis[v[l]]+a[v[l],i];
                        pre[i]:=v[l];
                        if not exist(v,l,r,i) then begin
                            v[r]:=i;
                            inc(r);
                        end;
                    end;
            inc(l);
        end;
    
    //print
    
        i:=n; j:=1;
        while i>0 do begin way[j]:=i; inc(j); i:=pre[i]; end; 
        way[0]:=j-1;
        
        
        exit(dis[y]);
    end;
    
    begin
        readln(n);
        for i:=1 to n do
            for j:=1 to n do
                read(a[i,j]);
        for i:=1 to n do
            for j:=1 to n do
                if (i<>j) and (a[i,j]=0) then a[i,j]:=INF; 
        ans:=spfa(1,n);
        for i:=way[0] downto 1 do write(way[i],' ');
        writeln;
        writeln(ans);
    end.
    
    
  • 0
    @ 2017-06-24 16:51:08
    //弱弱的floyd, 膜楼下大神
    #include <bits/stdc++.h>
    using namespace std;
    const int MAX = 1000000000;
    int dis[1005][1005];
    int path[1005][1005];
    int main()
    {
        int num;
        scanf("%d", &num);
        for(int i = 1; i <= num; i++)
            for(int k = 1; k <= num; k++)
                {
                    scanf("%d", & dis[i][k]);
                    if(dis[i][k] == 0)
                        dis[i][k] = MAX;
                    path[i][k] = k;
                }
        for(int k = 1; k <= num; k++)
            for(int i = 1; i <= num; i++)
                for(int j = 1; j <= num; j++)
                    if(dis[i][j] > dis[i][k] + dis[k][j])
                    {
                        dis[i][j] = dis[i][k] + dis[k][j];
                        path[i][j] = path[i][k];
                    }
        int st = 1, en = num;
        while(st != en)
        {
            printf("%d ", st);
            st = path[st][en];
        }
        printf("%d\n", en);
        printf("%d\n", dis[1][num]);
        return 0;
    }
    
    • @ 2017-10-27 14:50:18

      真的服你这个Floyed后继,卡点过,我用的Floyed前驱,TE了……

    • @ 2017-11-05 22:24:12

      过不去,害我wr了8次,赔我

  • 0
    @ 2016-09-07 13:41:02

    裸地SPFA。。
    不过就如楼下所说,数组开大点(╯3╰)。。。

    代码
    c++
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<queue>
    #define MAXV 2002
    #define MAXE 50010
    #define LL long long
    using namespace std;
    int T,n,m,u,v;
    bool vis[MAXV];
    LL dis[MAXV]={6000};
    long path[MAXV]={0},path1[MAXV]={0};
    struct Node
    {
    int to,next,w;
    };
    Node edge[MAXE];
    int idx,head[MAXV];
    void init()
    {
    idx=1;
    memset(head,0,sizeof(head));
    }
    void addEdge(int u,int v,int w)
    {
    edge[idx].to=v;
    edge[idx].w=w;
    edge[idx].next=head[u];
    head[u]=idx;
    idx++;
    }
    void visit(int sta)
    {
    for(int i=1;i<=n;i++)
    {
    vis[i]=0;
    dis[i]=6000;
    }
    queue<int>Q;
    Q.push(sta);
    vis[sta]=1;
    dis[sta]=0;
    while(!Q.empty())
    {
    int now=Q.front();
    Q.pop();
    vis[now]=0;
    for(int i=head[now];i;i=edge[i].next)
    {
    int w=edge[i].w;
    int son=edge[i].to;
    if(dis[now]+w<dis[son])
    {
    dis[son]=dis[now]+w;
    path[son]=now;//路径记录
    if(!vis[son])
    {
    Q.push(son); // 子节点未访问过
    vis[son]=1; // 标记已访问
    }
    }
    }
    }
    else
    {
    int k=n;
    for (int i=n;i>0;i--)
    {
    path1[i]=path[k];
    k=path[k];
    }
    for(int i=1;i<=n;i++)
    if (path1[i]!=0)
    cout<<path1[i]<<" ";
    cout<<n<<endl<<dis[n]<<endl;
    }//麻烦的路径还原。。请恕我愚昧
    }
    int main()
    {
    init();
    scanf("%d",&n);
    if (m==0 && n==0) { return 0; }
    for(int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    {
    int w;
    scanf("%d",&w);
    if (w != 0)
    addEdge(i,j,w);
    }
    visit(1);
    return 0;
    }

  • 0
    @ 2016-08-10 18:33:13

    数组开小了就太坑了!!害得我RE四次
    c++
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    int first[1005];
    struct edge{
    int point,next,len;
    } e[800005];
    int dis[1005], path[1005];
    int n;
    void add(int i, int u, int v, int w){
    e[i].point = v;
    e[i].next = first[u];
    e[i].len = w;
    first[u] = i;
    }
    void printpath(int k){
    if (path[k]!=0) printpath(path[k]);
    printf("%d ",k);
    }
    void spfa(int s){
    for (int j = first[s]; j; j = e[j].next) {
    if (dis[e[j].point]>dis[s]+e[j].len){
    dis[e[j].point]=dis[s]+e[j].len;
    path[e[j].point]=s;
    spfa(e[j].point);
    }
    }
    }
    int main(){
    int x, now=0;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    for (int j=1;j<=n;j++){
    scanf("%d",&x);
    if (x!=0) add(++now,i,j,x);
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    spfa(1);
    printpath(n);
    printf("\n%d",dis[n]);
    return 0;
    }

  • 0
    @ 2016-05-06 18:10:40

    裸的SPFA

    #include<iostream>
    #include<cstdio>
    #include<queue>
    #include<vector>
    #include<stack>
    using namespace std;
    const int inf = 1<<30;
    int n;
    int d[1100];
    int f[1100];
    bool in[1100];
    struct edge {
        int to;
        int val;
        edge (int a, int b) : to(a), val(b) {}
    };
    vector<edge> g[1100];
    queue<int> q;
    stack<int> ans;
    int main ()
    {
        //freopen ("in.txt", "r", stdin);
        cin >> n;
        int temp;
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++) {
                cin >> temp;
                if (temp) g[i].push_back(edge(j, temp));
            }
        for (int i = 1; i <= n; i++) d[i] = inf;
        d[1] = 0;
        in[1] = true;
        q.push(1);
        while (!q.empty()) {
            temp = q.front();
            q.pop();
            in[temp] = false;
            for (int i = 0; i < g[temp].size(); i++) {
                if (d[g[temp][i].to] > d[temp] + g[temp][i].val) {
                    d[g[temp][i].to] = d[temp] + g[temp][i].val;
                    f[g[temp][i].to] = temp;
                    if (!in[g[temp][i].to]) q.push(g[temp][i].to);
                }
            }
        }
        int p = n;
        while (p != 1) {
            ans.push(p);
            p = f[p];
        }
        cout << 1;
        while (!ans.empty()) {
            p = ans.top();
            ans.pop();
            cout << " " << p;
        }
        cout << endl << d[n];
        return 0;
    }
    
  • 0
    @ 2015-11-04 13:17:30

    此题数据太弱。上次手贱将运算符重载打错,小根堆变成大根堆居然还能AC。
    Dijkstra算法加STL priority_queue,使用邻接表存储。
    ##Block Code
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <climits>
    #include <queue>
    #define rep(i,l,r) for (int i=l; i<=r; i++)
    #define clr(x,y) memset(x,y,sizeof(x))
    #define travel(x) for (int i=last[x]; i; i=edge[i].pre)
    typedef long long ll;
    using namespace std;
    const int INF = 0x3f3f3f3f;
    const int maxn = 1010;
    struct Edge{
    int pre,to,cost;
    }edge[1000000];
    struct node{
    int dis,val;
    node(int x,int y){
    val = x; dis = y;
    }
    inline bool operator < (const node &p) const{
    return val > p.val;
    }
    };
    int n,z,temp,tot=0,top=0,d[maxn],last[maxn],pre[maxn],route[maxn];
    inline int read(){
    int ans = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)){
    if (c== '-') f = -1;
    c = getchar();
    }
    while (isdigit(c)){
    ans = ans * 10 + c - '0';
    c = getchar();
    }
    return ans * f;
    }
    inline void addedge(int x,int y,int z){
    edge[++tot].pre = last[x];
    edge[tot].to = y;
    edge[tot].cost = z;
    last[x] = tot;
    }
    void dijk(){
    priority_queue <node> q;
    clr(d,INF); d[1] = 0;
    q.push(node(1,0));
    while(!q.empty()){
    node now = q.top();
    q.pop();
    if (d[now.val] != now.dis) continue;
    travel(now.val){
    if (d[edge[i].to] > d[now.val] + edge[i].cost){
    d[edge[i].to] = d[now.val] + edge[i].cost;
    pre[edge[i].to] = now.val;
    q.push(node(edge[i].to,d[edge[i].to]));
    }
    }
    }
    }
    int main(){
    n = read(); clr(last,0);
    rep(i,1,n) rep(j,1,n){
    z = read();
    if (z) addedge(i,j,z);
    }
    dijk(); temp = n;
    while(temp){
    route[++top] = temp;
    temp = pre[temp];
    }
    for(int i=top; i>=2; i--) printf("%d ",route[i]);
    printf("%d\n",route[1]);
    printf("%d\n",d[n]);
    return 0;
    }

  • 0
    @ 2015-10-18 20:01:16

    大众,我提的是错的!!!!!!!!!!!

  • 0
    @ 2015-10-18 20:00:50

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #define IN 100000000
    const int maxn = 1000 + 5;
    using namespace std;
    int n,m,s,t,ll;
    int a[maxn][maxn],num[maxn],f[maxn][maxn],dis[maxn],ans[maxn],pre[maxn];
    bool vis[maxn];
    void find(int x)
    {
    if(pre[x]==x){
    printf("%d ",x);
    return;
    }
    find(pre[x]);
    printf("%d ",x);

    }

    void dijstra(int s)
    { int minn,k=0;
    for(int i=1;i<=n;i++)dis[i]=f[s][i];
    dis[s]=0;vis[s]=1;
    for(int i=1;i<n;i++)
    {
    minn=IN;
    for(int j=1;j<=n;j++)
    if(!vis[j]&&dis[j]<minn){k=j;minn=dis[j];}
    vis[k]=1;if(k==0)break;
    for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]>dis[k]+f[k][j]) {
    dis[j]=dis[k]+f[k][j]; pre[j]=k;

    }
    }
    }
    int main()
    {
    int yy;
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {
    cin>>f[i][j];
    if(f[i][j]==0)
    f[i][j]=IN;
    }
    for(int i=1;i<=n;i++)pre[i]=1;

    int v=n;

    dijstra(1);
    find(n);
    cout<<endl;
    cout<<dis[n];
    }

  • 0
    @ 2015-09-28 19:19:15

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define maxn 1001
    using namespace std;
    int f[maxn][maxn],c[maxn],pre[maxn];
    bool b[maxn];
    void find(int x)
    {
    if(pre[x]==x){
    printf("%d ",x);
    return;
    }
    find(pre[x]);
    printf("%d ",x);

    }
    int main()
    {
    int n,m,i,j,x,minn,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
    scanf("%d",&x);
    if(x==0){
    f[i][j]=709823562;
    }
    else{
    f[i][j]=x;
    }
    }
    }
    memset(c,127/3,sizeof(c));
    memset(b,false,sizeof(b));
    b[1]=true;
    for(i=1;i<=n;i++){
    c[i]=f[1][i];
    pre[i]=1;
    }
    for(i=1;i<=n;i++){
    minn=210000000;
    k=0;
    for(j=1;j<=n;j++){
    if(!b[j]&&c[j]<minn){
    minn=c[j];
    k=j;
    }
    }
    if(k==0){
    break;
    }
    b[k]=true;
    for(j=1;j<=n;j++){
    if(c[j]>c[k]+f[k][j]){
    c[j]=c[k]+f[k][j];
    pre[j]=k;
    }
    }
    }
    find(n);
    printf("\n");
    printf("%d",c[n]);
    return 0;
    }

  • 0
    @ 2015-07-24 17:53:23

    测试数据 #0: TimeLimitExceeded, time = 1031 ms, mem = 4280 KiB, score = 0
    测试数据 #1: TimeLimitExceeded, time = 1031 ms, mem = 4288 KiB, score = 0
    测试数据 #2: Accepted, time = 15 ms, mem = 4280 KiB, score = 15
    测试数据 #3: TimeLimitExceeded, time = 1031 ms, mem = 4284 KiB, score = 0
    测试数据 #4: Accepted, time = 62 ms, mem = 4284 KiB, score = 15
    测试数据 #5: TimeLimitExceeded, time = 1015 ms, mem = 4288 KiB, score = 0
    测试数据 #6: Accepted, time = 15 ms, mem = 4280 KiB, score = 5
    测试数据 #7: Accepted, time = 437 ms, mem = 4284 KiB, score = 5
    测试数据 #8: Accepted, time = 62 ms, mem = 4280 KiB, score = 5
    测试数据 #9: TimeLimitExceeded, time = 1031 ms, mem = 4280 KiB, score = 0
    TimeLimitExceeded, time = 5730 ms, mem = 4288 KiB, score = 45

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    int sq[1010][1010];
    int ming[1010][3];
    int n;
    void do_it(int k)
    {
    if(k==n)
    return;
    for(int i=1;i<=n;i++)
    {
    if(sq[k][i])
    {
    if(ming[i][1]>ming[k][1]+sq[k][i])
    {
    ming[i][1]=ming[k][1]+sq[k][i];
    ming[i][2]=k;
    do_it(i);
    }
    }
    }
    }
    void findway(int a)
    {
    if(a==0)
    return;
    findway(ming[a][2]);
    printf("%d ",a);
    }
    int main()
    {

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    ming[i][1]=INT_MAX;
    for(int j=1;j<=n;j++)
    {
    int a;
    scanf("%d",&a);
    if(a==0)
    continue;
    sq[i][j]=a;
    }
    }
    ming[1][1]=0;
    do_it(1);
    findway(ming[n][2]);
    printf("%d\n%d",n,ming[n][1]);
    }
    编译成功

    测试数据 #0: Accepted, time = 156 ms, mem = 8200 KiB, score = 15
    测试数据 #1: Accepted, time = 390 ms, mem = 8200 KiB, score = 15
    测试数据 #2: Accepted, time = 0 ms, mem = 8196 KiB, score = 15
    测试数据 #3: Accepted, time = 374 ms, mem = 8196 KiB, score = 15
    测试数据 #4: Accepted, time = 15 ms, mem = 8200 KiB, score = 15
    测试数据 #5: Accepted, time = 358 ms, mem = 8200 KiB, score = 5
    测试数据 #6: Accepted, time = 0 ms, mem = 8196 KiB, score = 5
    测试数据 #7: Accepted, time = 46 ms, mem = 8200 KiB, score = 5
    测试数据 #8: Accepted, time = 31 ms, mem = 8196 KiB, score = 5
    测试数据 #9: Accepted, time = 296 ms, mem = 8200 KiB, score = 5
    Accepted, time = 1666 ms, mem = 8200 KiB, score = 100
    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    int sq[1010][1010];
    int dist[1010];
    int queue[1001000];
    int minpast[1010];
    int n;
    void findway(int a)
    {
    if(a==0)
    return;
    findway(minpast[a]);
    printf("%d ",a);
    }
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    dist[i]=INT_MAX;
    for(int j=1;j<=n;j++)
    {
    int a;
    scanf("%d",&a);
    if(a==0)
    continue;
    sq[i][j]=a;
    }
    }
    dist[1]=0;
    int front=1;
    int back=2;
    queue[front]=1;
    for(;front<back;)
    {
    if(queue[front]==n)
    {
    front++;
    continue;
    }
    for(int i=1;i<=n;i++)
    {
    if(sq[queue[front]][i])
    if(dist[i]>dist[queue[front]]+sq[queue[front]][i])
    {
    dist[i]=dist[queue[front]]+sq[queue[front]][i];
    queue[back++]=i;
    minpast[i]=queue[front];
    }
    }front++;
    }
    findway(minpast[n]);
    printf("%d",n);
    printf("\n%d",dist[n]);
    }

  • 0
    @ 2015-07-03 12:14:42

    P1635城市连接
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1635 城市连接
    递交时间 2015-07-03 12:13:53
    代码语言 C++
    评测机 VijosEx
    消耗时间 777 ms
    消耗内存 4288 KiB
    评测时间 2015-07-03 12:13:55

    评测结果

    编译成功

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

    测试数据 #1: Accepted, time = 187 ms, mem = 4288 KiB, score = 15

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

    测试数据 #3: Accepted, time = 187 ms, mem = 4284 KiB, score = 15

    测试数据 #4: Accepted, time = 15 ms, mem = 4288 KiB, score = 15

    测试数据 #5: Accepted, time = 140 ms, mem = 4288 KiB, score = 5

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

    测试数据 #7: Accepted, time = 31 ms, mem = 4288 KiB, score = 5

    测试数据 #8: Accepted, time = 15 ms, mem = 4288 KiB, score = 5

    测试数据 #9: Accepted, time = 140 ms, mem = 4288 KiB, score = 5

    Accepted, time = 777 ms, mem = 4288 KiB, score = 100

    代码

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

    using namespace std;

    int n;
    int i , j , k;
    int a[1000 + 10][1000 + 10];
    int pre[1000 + 10];
    int use[1000 + 10];
    int dist[1000 + 10];
    int p[1000 + 10];
    int now;
    queue < int > q;

    int getpath( int x )
    {
    if( pre[x] < 0 )
    return x;
    p[i++] = x;
    return getpath( pre[x] );
    }

    int main()
    {
    scanf( "%d" , &n );
    for( i = 1 ; i <= n ; i++ )
    pre[i] = -1;
    for( i = 1 ; i <= n ; i++ )
    for( j = 1 ; j <= n ; j++ )
    scanf( "%d" , &a[i][j] );
    for( i = 1 ; i <= n ; i++ )
    for( j = 1 ; j <= n ; j++ )
    if( !a[i][j] )
    a[i][j] = 100000000;

    for( i = 1 ; i <= n ; i++ )
    dist[i] = 100000000;
    q.push( 1 );
    dist[1] = 0;
    while( !q.empty() )
    {
    now = q.front();
    q.pop();
    use[ now ] = 0;
    for( i = 1 ; i <= n ; i++ )
    if( dist[i] > dist[now] + a[now][i] )
    {
    dist[i] = dist[now] + a[now][i];
    pre[i] = now;
    if( !use[i] )
    {
    use[i] = 1;
    q.push(i);
    }
    }
    }
    i = 0;
    getpath( n );
    for( i = 0 ; p[i] != 0 ; i++ )
    ;
    printf( "1" );
    for( i-- ; i >= 0 ; i-- )
    printf( " %d" , p[i] );
    cout << endl;
    printf( "%d\n" , dist[n] );
    return 0;
    }

  • 0
    @ 2015-06-17 15:50:14

    C++要注意用标准输入输出,否则TLE。。。在这里卡了好久。。。

  • 0
    @ 2015-03-14 10:23:33

    #include<stdio.h>//TLE
    #include<string.h>
    int dist[1010][1010],map[1010];
    int min(int a,int b)
    {
    if(a>b)return b;
    else return a;
    }
    int main()
    {
    int n,i,j;
    int max=100000;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
    {
    scanf("%d",&dist[i][j]);
    if(dist[i][j]==0)dist[i][j]=max;
    }
    }
    int v[n];
    memset(v,0,sizeof(v));
    for(i=0;i<n;i++)map[i]=(i==0?0:max);
    for(i=0;i<n;i++)
    {
    int y,x,m=max;
    for(y=0;y<n;y++)
    {
    if(!v[y]&&map[y]<=m)
    m=map[x=y];
    }
    v[x]=1;
    for(y=0;y<n;y++)map[y]=min(map[y],map[x]+dist[x][y]);
    }
    int pre[n];
    memset(pre,0,sizeof(pre));
    int k=0;
    int count=1;
    int l=n-1;
    pre[k++]=n;
    while(count)
    {
    for(i=n-1;i>=0;i--)
    {
    if(i==0)count=0;
    if(map[i]+dist[i][l]==map[l])
    {
    l=i;
    pre[k++]=i+1;
    }
    }
    }
    for(i=k-1;i>=0;i--)
    printf("%d ",pre[i]);
    printf("\n");
    printf("%d",map[n-1]);
    return 0;
    }
    竟然会超时。。。。

  • 0
    @ 2015-02-10 18:21:12
    • 注意是**有向图**
    • 虽然题目没说,但要知道必须**从 1 出发走到 n **
    • 貌似没有无解情况

    上代码(鄙人只会用 Dijkstra,膜拜下面那些大神~)

    #include <stdio.h>
    #include <limits.h>
    int map[1000][1000];
    int dijkstra[1000],searched[1000],path[1000];
    void printPath(int index){
    //递归输出路径。若 index==0 ,则意味着回溯到了起点,可以开始返回
    if(index!=0)
    printPath(path[index]);
    //之所以要加一再输出是因为数组下标从零开始...
    printf("%d ",index+1);
    }
    int main(){
    int num;
    int i,k,source,min,index;
    scanf("%d",&num);
    for(i=0;i<num;i++){
    for(k=0;k<num;k++)
    scanf("%d",&map[i][k]);
    }
    for(i=0;i<num;i++){
    dijkstra[i]=LONG_MAX;
    searched[i]=path[i]=0;
    }
    //设置起始点为0(即题目中的1)
    path[0]=dijkstra[0]=0;
    source=0;
    for(i=1;i<num;i++){
    //把源点标记为“已找过”
    searched[source]=1;
    min=LONG_MAX;
    for(k=0;k<num;k++){
    if(!searched[k]){
    if(map[source][k]>0){
    if(dijkstra[k] > dijkstra[source]+map[source][k]){
    dijkstra[k]=dijkstra[source]+map[source][k];
    //记录一下路径(到达k点最优路径的上一个节点,亦即源点source)
    path[k]=source;
    }
    }
    if(min>dijkstra[k]){
    min=dijkstra[k];
    index=k;
    }
    }
    }
    source=index;
    }
    //从终点回溯输出路径
    printPath(num-1);
    //输出最优解
    printf("\n%d\n",dijkstra[num-1]);
    return 0;
    }

信息

ID
1635
难度
5
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
3394
已通过
1126
通过率
33%
被复制
1
上传者