Informatika gyűjtemény

Egy szinttel feljebb mt_tank.cs

2004050607080910

<<  13. óra  >>

<<  Gazdaságos tankolás  >>

NézetNyomtat

mt_tank.cs (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 2 KB
/*
 * Készítette a SharpDevelop.
 * Felhasználó: 02cmezei
 * Dátum: 2007.12.17.
 * Ido: 15:14
 * 
 * A sablon megváltoztatásához használja az Eszközök | Beállítások | Kódolás | Szabvány Fejlécek Szerkesztését.
 */
using System;
using System.IO;
using System.Collections.Generic;

namespace tank
{
    class Program
    {
        public class W
        {
            public int n;
            public int q;
            public byte[] p;
            public byte[,] d;
            public W(int n)
            {
                this.n=n;
                p=new byte[n];
                d=new byte[n,n];
            }
        }
        public struct Problem
        {
            public int c, s, e;
            public Problem(int c, int s, int e)
            {
                this.c=c;
                this.s=s;
                this.e=e;
            }
        }
        
        public static int Munka(Problem p)
        {           
            //Dijkstra...
            int[] t=new int[w.n*(p.c+1)];
            for (int i=0; i!=t.Length; i++) t[i]=int.MaxValue;
            t[p.s*(p.c+1)]=0;
            LinkedList<int> q=new LinkedList<int>();
            q.AddLast(p.s*(p.c+1));
            while(q.Count>0)
            {
                //a mag
                int r=q.First.Value; q.RemoveFirst();
                int v=r%(p.c+1); //a tank tartalma
                int f=r/(p.c+1); //az eredeti pont száma
                
                if (v!=p.c) if (t[r+1]>t[r]+w.p[f]) { t[r+1]=t[r]+w.p[f]; q.AddLast(r+1); }//tankolás
                
                for (int i=0; i!=w.n; i++)
                {
                    if ((v+1)>w.d[f,i]) //ha van út és elég benzin is
                    {
                        byte v2=(byte)(v-w.d[f,i]);
                        int r2=i*(p.c+1)+v2;
                        if (t[r2]>t[r]) //ha javítunk
                        {
                            t[r2]=t[r];
                            q.AddLast(r2);
                        }
                    }
                }
            }
            
            int min=int.MaxValue;
            for (int i=p.e*(p.c+1); i!=(p.e+1)*(p.c+1); i++) if (min>t[i]) min=t[i];
            return min;
        }

        static W w;
        static Problem[] problems;
        public static void Main(string[] args)
        {
            Beolvas("tank2.be");
            int[] mo=new int[problems.Length];
            for (int i=0; i!=problems.Length; i++)
            {
                mo[i]=Munka(problems[i]);
                Console.WriteLine(i+": "+mo[i]);
            }
            Kiir("tank2.ki", mo);
        }
        
        public static void Kiir(string oup, int[] mo)
        {
            TextWriter tw=new StreamWriter(oup);
            for (int i=0; i!=mo.Length; i++)
            {
                if (mo[i]==int.MaxValue)
                    tw.WriteLine("impossible");
                else
                    tw.WriteLine(mo[i]);
            }
            tw.Close();
        }
        
        public static void Beolvas(string inp)
        {
            TextReader tr=new StreamReader(inp);
            string[] l=tr.ReadLine().Split(' ');
            w=new W(int.Parse(l[0]));
            int m=int.Parse(l[1]);
            l=tr.ReadLine().Split(' ');
            
            //benzinárak
            for (int i=0; i!=w.n; i++) w.p[i]=byte.Parse(l[i]);
            //távolságok
            for (int i=0; i!=w.n; i++) for (int j=0; j!=w.n; j++) w.d[i, j]=255; //inicializálás, hogy lehessen táv is...
            for (int i=0; i!=m; i++)
            {
                l=tr.ReadLine().Split(' ');
                int x=int.Parse(l[0]);
                int y=int.Parse(l[1]);
                if (x!=y) //biztos ami bizos..
                {
                    w.d[x,y]=byte.Parse(l[2]);
                    w.d[y,x]=w.d[x,y];
                }
            }
            //kérdések...
            w.q=int.Parse(tr.ReadLine());
            problems=new Problem[w.q];
            for (int i=0; i!=w.q; i++)
            {
                l=tr.ReadLine().Split(' ');
                problems[i]=new Problem(int.Parse(l[0]),int.Parse(l[1]),int.Parse(l[2]));
            }
            tr.Close();
        }
    }
}
(Vissza)