diff options
Diffstat (limited to 'es4.cpp')
| -rw-r--r-- | es4.cpp | 67 |
1 files changed, 67 insertions, 0 deletions
@@ -0,0 +1,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;
+}
|