1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#include <iostream>
#define BIANCO 0 //Non Visitato
#define NERO 2 //Visitato
#define GRIGIO 1 //Non Finito
#define INF 999999
#include <vector>
#include <fstream>
#include <queue>
#define MAXN 9999
#define INDEF -1
#include <stack>
using namespace std;
typedef pair<int,int> p;
int V,E;
struct nodo {
vector <p> adj;
int dist;
nodo(){
dist=INF;
}
}no[MAXN];
int colore[MAXN];
void relax (nodo no[], int u, int z)
{
p v= no[u].adj[z];
if (no[v.first].dist> no[u].dist + v.second )
{
no[v.first].dist= no[u].dist + v.second;
}
}
void bf (nodo no[],int n, int s)
{
int i,j,z;
no[0].dist=0;
for (i=0;i<V;i++) //Scorro
{
for (j=0;j<V;j++)
{
for (z=0;z<no[j].adj.size();z++)
{
relax(no,j,z);
}
}
}
}
int main(int argc, char** argv) {
ifstream in ("input.txt");
ofstream out ("output.txt");
in>>V>>E;
int a,b,c;
for (int i=0;i<E;i++)
{
in>>a>>b>>c;
no[a].adj.push_back(p(b,c));
}
bf(no,V,0); //Adiacenze, numeri di vertici, sorgente
for (int i=0;i<V;i++)
{
cout<<no[i].dist<<endl;
}
return 0;
}
|
