Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXINT = 1000000007;
- int d2[101][101]; // "plus nieskończoność"
- int main()
- {
- // Macierz minimalnych kosztów dojścia
- int n,m,x,y,w,kr;
- int **d;
- cin >> n >> kr>> m;
- d = new int * [n+1]; // Czytamy liczbę wierzchołków oraz krawędzi
- // Tworzymy dynamiczną macierz d
- for(int i = 1; i <= n; i++)
- {
- d[i] = new int [n+1]; // Tworzymy wiersz macierzy
- for(int j = 1; j <=n; j++)
- d[i][j] =INT_MAX; // Wiersz wypełniamy największą liczbą dodatnią
- d[i][i] = 0; // Jednakże na przekątnej wpisujemy 0
- }
- for(int i = 1; i <=kr; i++)
- {
- cin >> x >> y >> w; // Czytamy definicję krawędzi
- d[x][y]=min(d[x][y],w);
- d[y][x]=min(d[y][x],w); // Wagę krawędzi umieszczamy w macierzy d
- }
- // Algorytm Floyda-Warshalla
- for(int k = 1; k <=n; k++)
- for(int i = 1; i <=n; i++)
- for(int j = 1; j <=n; j++)
- {
- w = d[i][k] + d[k][j];
- if(d[i][j] > w) d[i][j]=min(d[i][j],w),d[j][i]=min(d[i][j],w);
- }
- for(int i=1;i<=m;i++)
- {
- for (int hh=1; hh<=n; hh++)
- {
- for (int jj=1; jj<=n; jj++)
- d2[hh][jj]=d[hh][jj];
- }
- cin>>x>>y>>w;
- d2[x][y]=w;
- d2[y][x]=w;
- for(int k=1;k<=n;k++)
- {
- for(int r=1;r<=n;r++)
- {
- if (d2[k][r] > d2[k][x] + d2[x][y] + d2[y][r])
- d2[k][r]=d2[k][x] + d2[x][y] + d[y][r], d2[k][r]=d2[r][x] + d2[x][y] + d[y][r];
- if( d2[k][r] > d2[k][y] + d2[y][x] + d2[x][r])
- d2[k][r]=d2[k][y] + d2[y][x] + d2[x][r], d2[r][k]=d2[k][y] + d2[y][x] + d2[x][r];
- }
- }
- if(d2[1][n]<d[1][n])
- {
- printf("1\n");
- for(int j=1;j<=n;j++)
- for(int r=1;r<=n;r++)
- {
- d[j][r]=d2[j][r];
- }
- }
- else
- {
- printf("0\n");
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement