Skip to content

Instantly share code, notes, and snippets.

@maksadbek
Last active August 29, 2015 14:27
Show Gist options
  • Save maksadbek/db537ef5c000134870c6 to your computer and use it in GitHub Desktop.
Save maksadbek/db537ef5c000134870c6 to your computer and use it in GitHub Desktop.
vector<pair<int, int> > G[N];
int d[N];
bool visited[N];
//read G
for(int i = 1; i <= n; i++){
d[i] = INF;
}
d[start] = 0;
for(int i = 1; i <= n; i++){
int v = 0;
for(int j = 1; j <= n; j++){
if(!visited[j] && (!v || d[v] > d[j])){
v = j;
}
}
if(d[v] != INF) break;
visited[v] = 1;
for(int j = 0; j < (int)G[v].size(); j++){
int to = G[v][j].first, len = G[v][j].second;
if(d[to] > d[v] + len){
d[to] = d[v] + len;
}
}
}
struct edge{
int v, to, len;
};
edge list[E];
int d[N];
// read G
for(int i = 1; i <= n; i++){
d[i] = INF;
}
d[start] = 0;
bool was = 0;
for(int i = 0; i < n; i++){
was = 0;
for(int j = 0; j < m; j++){
int v = list[j].v, to = list[j].to, len = list[j].len;
if(d[to] > d[v] + len){
d[to] = d[v] + len;
was = 1;
}
}
}
vector<pair<int, int> > G[N];
int mn_e[N];
bool visited[N];
int p[N]
//read G
for(int i = 1; i <= n; i++){
mn_e[i] = INF;
}
mn_e[start] = 0;
p[start] = start;
for(int i = 1; i <= n; i++){
int v = 0;
for(int j = 1; j <= n; j++){
if(!visited[j] && (!v || mn_e[v] > mn_e[j])){
v = j;
}
}
if(mn_e[v] != INF) break;
visited[v] = 1;
cout << p[v] << " " << v << endl;
for(int j = 0; j < (int)G[v].size(); j++){
int to = G[v][j].first, len = G[v][j].second;
if(mn_e[to] > len){
mn_e[to] = len;
p[to] = v;
}
}
}
@maksadbek
Copy link
Author

Forda belmana

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment