Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- ifstream fin("roy-floyd.in");
- ofstream fout("roy-floyd.out");
- int n,a[1002][1002],l[1002][1002],ramase[1002],primul[1002];
- void scrie(int a[][1002])
- {
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- {
- cout<<a[i][j]<<" ";
- }
- cout<<endl;
- }
- cout<<endl;
- }
- void drum(int i,int j)
- {
- int ok=0;
- //cout<<i<<" "<<j<<endl;
- //cin.get();
- for(int k=1;k<=n && !ok;k++)
- {
- if(a[i][j]==a[i][k]+a[k][j] && k!=i && k!=j)
- {
- ok=1;
- drum(i,k);
- drum(k,j);
- }
- }
- if(!ok)
- {
- fout<<j<<" ";
- }
- }
- int main()
- {
- memset(a,10,sizeof(a));
- int infinit=a[0][0];
- int i,j,cost;
- fin>>n;
- while(fin>>i>>j>>cost)
- {
- a[i][j]=cost;
- l[i][j]=1;
- }
- for(int i=1;i<=n;i++)
- {
- a[i][i]=0;
- }
- for(int k=1;k<=n;k++)
- {
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- {
- if(a[i][j]>a[i][k]+a[k][j] && i!=k && j!=k)
- {
- a[i][j]=a[i][k]+a[k][j];
- l[i][j]=l[i][k]+l[k][j];
- }
- }
- }
- scrie(a);
- }
- int afis;
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- {
- if(a[i][j] && a[i][j]!=infinit)
- {
- if(l[i][j]>1)
- {
- //fout<<i<<"->"<<j<<": "<<i<<" ";
- fout<<i<<" ";
- drum(i,j);
- fout<<endl;
- }
- //fout<<i<<" ";
- //l[i][j]++;
- //fout<<endl;
- }
- else
- {
- //cout<<i<<" "<<j<<endl;
- }
- }
- }
- //for(int i=1;i<=n)
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- {
- cout<<l[i][j]<<" ";
- }
- cout<<endl;
- }
- /*for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- {
- cout<<a[i][j]<<" ";
- }
- cout<<endl;
- }*/
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement