1 条题解

  • 0
    @ 2025-2-14 21:30:05

    C :

    #include <stdio.h>
    int main()
    {
        char E[501][501]={0},chr,p[501]={0};
        int V[501],N,i,j,l,m,t[500]={0};
        scanf("%d%d",&i,&N);
        while (scanf("%c",&chr)!=EOF)
        {
            if (chr=='\n') l=1;
            if (scanf("%d",&m)==EOF) break;
            for (i=1;i<l;i++) E[t[i]][m]=1;
            t[l++]=m;
        }
        for (i=2;i<=N;i++) V[i]=1<<26;
        V[1]=0;
        for (i=0;i<N;i++)
        {
            for (m=1;p[m];m++);
            for (j=m+1;j<=N;j++)
                if (p[j]==0&&V[m]>V[j]) m=j;
            p[m]=1;
            for (j=1;j<=N;j++)
                if (p[j]==0&&E[m][j]&&V[m]+1<V[j]) V[j]=V[m]+1;
        }
        if (V[N]==1<<26) printf("NO");
        else printf("%d",V[N]==0?0:V[N]-1);
        return 0;
    }
    

    C++ :

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    int a[501][501]={0},dis[501];
    int m,n;
    void init();
    void spfa(int);
    int main()
    {
    	//freopen("Travel5.in","r",stdin);
    	init();
    	spfa(1);
    	if(dis[n]==0x7f7f7f7f)cout<<"NO"<<endl;
    	else cout<<dis[n]-1<<endl;
    	return 0;
    }
    void init()
    {
    	cin>>m>>n;
    	getchar();	
    	for(int i=1;i<=m;i++)
    	{
    		int temp[501],len=0,lens=0,x;
    		string s;
    		getline(cin,s);
    		while(lens<s.size())
    		{
    			while(s[lens]==' ') lens++;
    			x=0;
    			while(s[lens]>='0' && s[lens]<='9')
    			{
    				x=10*x+s[lens]-48;
    				lens++;
    			}
    			temp[++len]=x;
    			//cout<<x<<' ';			
    		}
    		//cout<<endl;
    		/*char ch=1;
    		while(ch!=10)//10是换行的asscall值
    		{
    			cin>>temp[++len];
    			ch=getchar();
    		} */
    		for(int j=1;j<len;j++)
    			for(int k=j+1;k<=len;k++)a[temp[j]][temp[k]]=1;
    		
    	}
    }
    void spfa(int x)
    {
    	queue<int> q;
    	bool flag[501]={0};
    	memset(dis,0x7f,sizeof(dis));
    	q.push(x);
    	flag[x]=true;
    	dis[x]=0;
    	while(!q.empty())
    	{
    		int k=q.front();
    		for(int i=1;i<=n;i++)
    		{
    			if(a[k][i]>0 && dis[i]>a[k][i]+dis[k])
    			{
    				dis[i]=dis[k]+a[k][i];
    				if(!flag[i])
    				{
    					q.push(i);
    					flag[i]=true;
    				}
    			}
    		}
    		flag[k]=false;
    		q.pop();
    	}
    }
    

    Pascal :

    program travel;
    type list=record x,z,n:longint; end;
    var k:array[0..500]of longint;
        f:array[0..1000000]of longint;
    	e:array[1..100000]of list;
    	d:array[0..500]of longint;
    	v:array[0..500]of boolean;
    	min,n,m,o:longint;
    procedure add(a,b,c:longint);
      begin
        inc(o);
    	e[o].x:=b;
    	e[o].z:=c;
    	e[o].n:=k[a];
    	k[a]:=o;
      end;
    procedure init;
      var i,j,k,l:longint;
          a:array[1..100]of longint;
      begin
        readln(m,n);
    	for l:=1 to m do
    	  begin
    	    k:=0;
    	    while not eoln do
    	      begin
    		    inc(k);
    			read(a[k]);
    		  end;
                  readln;
    		for i:=1 to k-1 do
    		  for j:=i+1 to k do
    		    if i<>j then add(a[i],a[j],1);
    	  end;
      end;
    procedure spfa;
      var head,tail,now,t:longint;
      begin
        f[1]:=1;
    	head:=0;
    	tail:=1;
    	v[1]:=true;
            fillchar(d,sizeof(d),127);
            d[1]:=0;
    	while head<tail do
    	  begin
    	    inc(head);
    		now:=f[head];
    		v[now]:=false;
    		t:=k[now];
    		while t<>0 do
    		  begin
    		    if d[now]+e[t].z<d[e[t].x] then
    			  begin
    			    d[e[t].x]:=d[now]+e[t].z;
    				if not v[e[t].x] then
    				  begin
    				    v[e[t].x]:=true;
    					inc(tail);
    					f[tail]:=e[t].x;
    				  end;
    			  end;
    			t:=e[t].n;
    		  end;
    	  end;
    	if d[n]=2139062143 then writeln('NO') else
    	writeln(d[n]-1);
      end;
    begin
      while not eof do begin
      init;
      if (m=0)and(n=0) then begin close(input);close(output);halt;end;
      spfa;
      end;
      close(input);close(output);
    end.
    
    • 1

    信息

    ID
    948
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者