Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker,"/STACK:100000000000,100000000000")
- #include <bits/stdc++.h>
- #define ll long long
- #define pb push_back
- #define mp make_pair
- #define D double
- #define pi pair<int,int>
- #define si set <pi>
- #define F first
- #define S second
- #define forn(i,n) for (int(i)=0;(i)<(n);i++)
- #define forr(i,x,y) for (int(i)=(x);(i)<=(y);i++)
- #define ford(i,x,y) for (int(i)=(x);(i)>=(y);i--)
- #define rev reverse
- #define in insert
- #define er erase
- #define all(n) (n).begin(),(n).end()
- #define graf vector<vector<pi> >
- #define graf1 vector<vector<ll> >
- #define sqr(a) (a)*(a)
- #define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
- #define y1 asdadasdasd
- const int INF=1e9;
- const D cp=2*asin(1.0);
- const D eps=1e-9;
- const ll mod=1000000000;
- using namespace std;
- int n; // number of vertex
- int s; // start node
- int a[101][101]; // graph
- int d[101]; // minimal distance from start vertex to all another nodes
- char used[101];
- int main()
- {
- cin.tie(0);
- ios_base::sync_with_stdio(false);
- cin>>n;
- forn(i,n)
- forn(j,n)
- {
- cin>>a[i][j];
- if (a[i][j]==-1) a[i][j]=INF; // there's no road from i to j
- }
- cin>>s;
- forn(i,n) d[i]=INF,used[i]=false;
- d[s]=0;
- forn(k,n)
- {
- int _min=INF,x=-1;
- forn(i,n)
- if (!used[i] && _min>d[i]) _min=d[i],x=i;
- if (x==-1) break;
- used[x]=true;
- forn(i,n)
- if (d[i]>d[x]+a[x][i]) d[i]=d[x]+a[x][i];
- }
- forn(i,n) cout<<((d[i]==INF)?-1:d[i])<<' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement