Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<fstream>
- #include<vector>
- #define inf 2000000000
- using namespace std;
- ifstream fin ("prog.in");
- ofstream fout ("prog.out");
- struct q
- {
- int nod, c;
- };
- vector< vector<q> > a;
- vector<int> d;
- vector<int> t;
- vector<bool> sel;
- int n;
- void creare()
- {
- fin>>n;
- a.resize(n+1);
- int i;
- q x;
- while(fin>>i>>x.nod>>x.c)
- {
- a[i].push_back(x);
- }
- d.resize(n+1,inf);
- t.resize(n+1);
- sel.resize(n+1);
- }
- void dijkstra(int sur)
- {
- int i,j,k,nod;
- sel[sur]=1;
- for(i=0;i<a[sur].size();i++)
- {
- d[a[sur][i].nod]=a[sur][i].c;
- t[a[sur][i].nod]=sur;
- }
- for(i=1;i<=n;i++)
- {
- int minn;
- minn=inf;
- for(j=1;j<=n;j++)
- if(sel[j]==0&&d[j]<minn)
- {
- minn=d[j];
- nod=j;
- }
- sel[nod]=1;
- for(j=0;j<a[nod].size();j++)
- if(sel[a[nod][j].nod]==0&&d[a[nod][j].nod]>a[nod][j].c+d[nod])
- {
- d[a[nod][j].nod]=a[nod][j].c+d[nod];
- t[a[nod][j].nod]=nod;
- }
- }
- }
- void afisare(int nod)
- {
- int no=t[nod];
- afisare(no);
- fout<<nod<<' ';
- }
- int main ()
- {
- creare();
- dijkstra(1);
- // afisare(5);
- int nod=5;
- while(t[nod]!=1)
- {
- fout<<nod<<' ';
- nod=t[nod];
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement