Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #define INF 1000000007
- using namespace std;
- ifstream f("dijkstra.in");
- ofstream g("dijkstra.out");
- int viz[50005], dist[50005];
- vector<int> graph[50005];
- vector<int> graphC[50005];
- void Dijkstra (int n)
- {
- for(int i=2; i<=n; i++)
- dist[i] = INF;
- int idx;
- for(int t=1; t<=n; t++)
- {
- int mini = INF;
- for(int i=1; i<=n; i++)
- if(!viz[i] && dist[i] < mini)
- {
- mini = dist[i];
- idx = i;
- }
- viz[idx] = 1;
- int dim = graph[idx].size();
- for(int i=0; i<dim; i++)
- {
- int vecin = graph[idx][i];
- int cost = graphC[idx][i];
- if(dist[idx] + cost < dist[vecin])
- dist[vecin] = dist[idx] + cost;
- }
- }
- }
- int main ()
- {
- int n, m, a, b, c;
- f>>n>>m;
- dist[1] = 0;
- for(int i=1; i<=m; i++)
- {
- f>>a>>b>>c;
- graph[a].push_back(b);
- graphC[a].push_back(c);
- }
- Dijkstra(n);
- for(int i=2; i<=n; i++)
- {
- if(dist[i] == INF)
- g<<0;
- else
- g<<dist[i]<<" ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement