Cod sursa(job #445268)

Utilizator serbanlupulupulescu serban serbanlupu Data 23 aprilie 2010 12:37:04
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 6.96 kb
Raporteaza aceasta sursa 
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  <meta http-equiv="Content-Style-Type" content="text/css">
  <title></title>
  <meta name="Generator" content="Cocoa HTML Writer">
  <meta name="CocoaVersion" content="949.54">
  <style type="text/css">
    p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica}
    p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; min-height: 14.0px}
    span.Apple-tab-span {white-space:pre}
  </style>
</head>
<body>
<p class="p1">#include &lt;iostream&gt;</p>
<p class="p1">#include &lt;fstream&gt;</p>
<p class="p1">#include &lt;vector&gt;</p>
<p class="p1">#include &lt;algorithm&gt;</p>
<p class="p1">#include &lt;queue&gt;</p>
<p class="p2"><br></p>
<p class="p1">#define oo 0x3f3f3f3f</p>
<p class="p2"><br></p>
<p class="p1">using namespace std;</p>
<p class="p2"><br></p>
<p class="p1">int nodes;</p>
<p class="p1">vector &lt; vector &lt; pair &lt; int, int &gt; &gt; &gt; List;</p>
<p class="p2"><br></p>
<p class="p1">void read(const char * buff_file)</p>
<p class="p1">{</p>
<p class="p1"><span class="Apple-tab-span">	</span>fstream f(buff_file, ios::in);</p>
<p class="p1"><span class="Apple-tab-span">	</span>f&gt;&gt;nodes;</p>
<p class="p1"><span class="Apple-tab-span">	</span>int edges;</p>
<p class="p1"><span class="Apple-tab-span">	</span>f&gt;&gt;edges;</p>
<p class="p1"><span class="Apple-tab-span">	</span>List.reserve(nodes+1);</p>
<p class="p1"><span class="Apple-tab-span">	</span>List.resize(nodes+1);</p>
<p class="p2"><span class="Apple-tab-span">	</span></p>
<p class="p1"><span class="Apple-tab-span">	</span>int left, right, value;</p>
<p class="p2"><span class="Apple-tab-span">	</span></p>
<p class="p1"><span class="Apple-tab-span">	</span>for (int i=1; i&lt;=edges; ++i)</p>
<p class="p1"><span class="Apple-tab-span">	</span>{</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>f&gt;&gt;left&gt;&gt;right&gt;&gt;value;</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>List[left].push_back(make_pair(right, value));</p>
<p class="p1"><span class="Apple-tab-span">	</span>}</p>
<p class="p1"><span class="Apple-tab-span">	</span>f.close();</p>
<p class="p1">};</p>
<p class="p2"><br></p>
<p class="p1">int used[50005];</p>
<p class="p1">int dest[50005];</p>
<p class="p2"><br></p>
<p class="p1">struct cmp</p>
<p class="p1">{</p>
<p class="p1"><span class="Apple-tab-span">	</span>bool operator()(const int &amp;left, const int &amp;right) const</p>
<p class="p1"><span class="Apple-tab-span">	</span>{</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>if (dest[left] &lt; dest[right])</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>return 0;</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>else</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>return 1;</p>
<p class="p1"><span class="Apple-tab-span">	</span>}</p>
<p class="p1">};</p>
<p class="p2"><br></p>
<p class="p1">int nr;</p>
<p class="p2"><br></p>
<p class="p1">void Dijkstra()</p>
<p class="p1">{</p>
<p class="p1"><span class="Apple-tab-span">	</span>priority_queue&lt;int, vector&lt;int&gt;, cmp&gt; Q;</p>
<p class="p1"><span class="Apple-tab-span">	</span>for (int i=1; i&lt;=nodes; ++i)</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>dest[i]=oo;</p>
<p class="p1"><span class="Apple-tab-span">	</span>dest[1]=0;</p>
<p class="p1"><span class="Apple-tab-span">	</span>Q.push(1);</p>
<p class="p1"><span class="Apple-tab-span">	</span>for ( ; !Q.empty(); )</p>
<p class="p1"><span class="Apple-tab-span">	</span>{</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>int x=Q.top();</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>Q.pop();</p>
<p class="p2"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span></p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>for (vector&lt; pair &lt; int, int &gt; &gt;::iterator it=List[x].begin(); it &lt; List[x].end(); it++)</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>{</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>if (dest[it-&gt;first] &gt; dest[x] + it-&gt;second)</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>{</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>dest[it-&gt;first]=dest[x]+it-&gt;second;</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>Q.push(it-&gt;first);</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>}</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>}</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>}</p>
<p class="p1">}</p>
<p class="p2"><br></p>
<p class="p2"><br></p>
<p class="p1">void print(const char * out_file)</p>
<p class="p1">{</p>
<p class="p1"><span class="Apple-tab-span">	</span>fstream g(out_file, ios::out);</p>
<p class="p1"><span class="Apple-tab-span">	</span>for (int i=2; i&lt;=nodes; ++i)</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>if (dest[i] == oo)</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>g&lt;&lt;"0 ";</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>else</p>
<p class="p1"><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span><span class="Apple-tab-span">	</span>g&lt;&lt;dest[i]&lt;&lt;" ";</p>
<p class="p1">}</p>
<p class="p2"><br></p>
<p class="p1">int main()</p>
<p class="p1">{</p>
<p class="p1"><span class="Apple-tab-span">	</span>read("dijkstra.in");</p>
<p class="p1"><span class="Apple-tab-span">	</span>Dijkstra();</p>
<p class="p1"><span class="Apple-tab-span">	</span>print("dijkstra.out");</p>
<p class="p1"><span class="Apple-tab-span">	</span>return 0;</p>
<p class="p1">};</p>
</body>
</html>