Pagini recente » Cod sursa (job #2292114) | Cod sursa (job #2001321) | Cod sursa (job #2989761) | Cod sursa (job #2848428)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;
ifstream fin("tunel.in");
ofstream fout("tunel.out");
struct nodul {
int nod, cost;
};
const double eps = 0.0000001;
int n, m;
double mat[260][260], sol[260];
vector <nodul> G[260];
void schimb(int a, int b)
{
for(int i = 1; i <= n; i++)
swap(mat[a][i], mat[b][i]);
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y, c;
fin >> x >> y >> c;
G[x].push_back({y, c});
G[y].push_back({x, c});
}
for(int nod = 1; nod < n; nod++)
{
int nr_vec = G[nod].size(), total = 0;
for(nodul vecin : G[nod])
{
total += vecin.cost;
if(vecin.nod != n)
mat[nod][vecin.nod] = (double) 1 / nr_vec;
}
mat[nod][nod] = -1;
mat[nod][n] = - (double) total / nr_vec;
}
int i = 1, j = 1;
while(i <= n - 1 && j <= n - 1)
{
int k;
for(k = i; k < n; k++)
if(mat[k][j] < -eps || mat[k][j] > eps)
break;
if(k == n)
{
j++;
continue;
}
if(k != i)
schimb(k, i);
for(k = j + 1; k <= n; k++)
mat[i][k] = mat[i][k] / mat[i][j];
mat[i][j] = 1;
for(k = i + 1; k < n; k++)
{
for(int l = j + 1; l <= n; l++)
mat[k][l] -= mat[k][j] * mat[i][l];
mat[k][j] = 0;
}
i++, j++;
}
for(i = n - 1; i > 0; i--)
{
for(int j = 1; j <= n; j++)
{
if(mat[i][j] > eps || mat[i][j] < -eps)
{
if(j == n)
{
fout << "Imposibil";
return 0;
}
sol[j] = mat[i][n];
for(int k = j + 1; k <= n - 1; k++)
sol[j] -= sol[k] * mat[i][k];
break;
}
}
}
fout << fixed << setprecision(8) << sol[1];
return 0;
}
/*
.::////++ossss+. `++:``
-md+ohddhhhhhhMM/ oMMMNds+-`
`/dh` /M: `::://///mMo `hMm+oydmmNhs/-`
`:hNNM/ /M+ -:://///hMh `mMy/////+oydMNd`
`/dNmsoMd` :Mm.`.-:://///yMd`.MM+////////oNMy`
`/hNms///dM: :MN/--::::////oMm.-MN/////////dMN-
`/hNms/////oMd`-NN+::::::////+mNhhMh////////oMMo
yMNy////////dMhdNm/:::::://////+oss/////////mMm.
/NNs////////oddyo/::::::://////////////////sMM+
`+NMs//////////::::::::::://///////////////mMh`
`+NMs//////////::::::::::////////////////sMN:
`+MNo/////////::::::::::////////////////mMs`
`+MNo/////////:::::::::///////////////sMm.
oMN+////////:::::::::///////////////NM/
oMm+/////////+ooooosssssssssooo+//yMh
`oMm+////+osssssssssssssssssssssssNN.
`oMm+/osssssssssssssssssssssssssdM/
`+NmysssssssssssssssssssssssshNMs
-hMmhyssssssssssssssssyhdNNho-`
`-ohmNmmdddddddmmmmmhys+-``
``.-:://///::-..```
````..--:://++oosyyhh+`
``` .+osyyhdmmmmmmmmmmddddhyyshMM/
-sdmdy. -dMdhyyysooo+++/////::///:::yMm--os+-`
.dMMMMm-/mMmyhddd+::::::::::::omNmmdyohMmNMMMNo
+MMMMMNmMMMMMMMMMs::::::::::::sMMMMMMMNMMMMMMMm.
oMMMMMMMMMMMMMMNd/::::::::::::+mNMMMMMMMMMMMMMM:
/NMMMMMMMMNNmdyo/:::::/+++/::::/ohmmNMMMMMMMMMN-
`+hmNNdhyso+/::::::++:+ooo/::+::::/+oyhdmNNNNNy`
:mMy/:::::::::::/M+::::::::y::::::::://+oNMs`
`/NNs:/shhs/::::::+M:::::::::y:::::::/+//::sMm-
``````oNNo:oNMMMMNy:::::+M:::::::::y:::::+hNMMmo::hMh` ````
`.:oydddhhMm+:/yyyhmMMMy::::+M:::::::::y::::sNMMMMMMo:/dMs``/oosssso/-`
`+hNMNNNNNNNm/:::::://+ymN/:::+N:::::::::y:::sNmhso++sy::/mM+sMNNNNNNNNNh-
+MMNNNNNNNNNd/::::::+sso:o::::+N:::::::::y:::+/+ss+:::::::+NMNNNNNNNNNNNMy
+MMNNNNNNNNNNs::::::::::+ooo/:/+:::::::::dyyssso:::::::::::oNNNNNNNNNNNNMh
-MMMNNNNNNNNNmdddhhhyyyNds//:::::::::::::///+sdNmhhhhhhhddddNNNNNNNNNNNNMo
`dMMMMMMNNNNNNNNNNNNNNMm/::::::::::::::::::::::/mMNNNNNNNNNNNNNNNNNNMMMMN-
:NMMMMMMMMMMMMMMMMMMMMMmyo+//:::::::::::::://+odMMMMMMMMMMMMMMMMMMMMMMM+`
+MNNmNMMMMMMMMMMMMMMMMMMMMNNNNmddhhhhhddmNNNMMMMMMMMMMMMMMMMMMMMMMMNd/`
:mMdh/.-::/+ooosssyyyhhhhhhhhhddddddddddddddddddddhhhyyssooo+/:ydmMMm.
`oNMNhhy: `` `````````````````````````` `+hhhNMMm/`
-hMMNmhhhyo. `` ` `` -shhhhmNMMNs`
`+mMMNNmhhhhhyo-` `` . `` .:shhhhhhmNNNMMh.
.yMMNNNNmhhhhhhhhs+-.` `` . ` `-/oyhhhhhhhhmNNNNMMd:
:dMMNNNNNmhhhhhhhhhhhyso/:-.`` ` ``..-/+oyyhhhhhhhhhhhNNNNNNMMN+
`+NMMNNNNNNmhhhhhhhhhhhhhhhhyyssso+++//////://///+++osssyyhhhhhhhhhhhhhhhhhNNNNNNMMMN-
`sMMMMMNNNNNNhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhdNNNNNMMMMMs
.MMMMMMMMNNNNdhhhhhhhhhhhhhhhhhhhhhhhhhhhdddhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhmNNNMMMMMMN:
`+NMMMMMMMNNNmhhhhhhhhhhhhhhhhhhhhhhddmmmmmdhhhmmmmmdhhhhhhhhhhhhhhhhhhhhhdNNNMMMMMMm:
.yNMMMMMMMNNd/syhhhhhhhhhhhhhhhhdmmmmmmmdhhhhdmmmmdhsssssyyhhhhhhhhhhyyomNNMMMMMMh.
:dMMMMMMMMNs`.+shhhhhhhhhhysssssssyyhhhhhhhmmdysssssssssssyhhhhhhs/.`hNMMMMMMMs`
`+NMMMMMMMMh. .:+syhhhhsssssssssssssssshddssssssssssssssshys+:` `hMMMMMMMN/`
.sMMMMMMMMN/ `-:+oooosssssssssssssssssssssssooo+//:-.` -mMMMMMMMM/
:MMMMMMMMMd: ` ```....-----------...```` ` `sNMMMMMMMNMd`
`sMMmMMMMMMMMh/` .oNMMMMMMMNdhMM+
/MMmyhmMMMMMMMMmo- `` `:sNMMMMMMMNdhyymMN-
.mMmyyyyhmNMMMMMMMNdo:` `` `:odNMMMMMMMNdhyyyyyNMh`
`hMMysyyyyyhdNMMMMMMMMNmy+:.` `` `.:+hmNMMMMMMMMNdhyyyyssshMMo
oMMhssssyyyyyyhdNMMMMMMMMMNNmhs+/:---.-----://oyhmNNMMMMMMMMMNmhhyyyyysssssdMN:
:NMdsssssssyyyyyyhhmNMMMMMMMMMMMMMMNNNNmNNNNNMMMMMMMMMMMMMMMNdhyyyyyysssssssyNMd`
.mMNmdhyssssssyyyyyyyhdmNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMNmhhyyyyyssssssssyyhNMMo
`yMNyyhdmmhyssssssyyyyyyyhhdmMMMMMMMMMMMMMMMMMMMMMMMMMMMmdhhyyyyyyssssssyyhmmdhyhMN-
+MMdsssssyhddhyysssssyyyyyyooshmNMMMMMMMMMMMMMMMMMMMNmhsooyyyyysssssyyddmmhyyssssmMd`
-NMmsssssssssyyhddhyyssssyysooooosydNNMMMMMMMMMMMMNdysooooosysssyyhdmmdhysssssssssyNMo
`dMNyssssssssssssssyhhdhhyys++++ooooooshmNMMMMMNmhsoooooo++++yhddddhyysssssssssssssshMN-
`sMMhsssssssssssssssssssyyhhdhysoooooooooooyhddysoooooooosyyhhhhyyssssssssssssssssssssmMd`
/MMmssssssssssssssssssssssssssyyhhdddddhhhhyyyhyyyhhhhhhhyysssssssssssssssssssssssssssyMMo`
-NMNysssssssssssssssssssssssssssssssssssyyyhhhhyyyysssssssssssssssssssssssssssssssssssssdMN-
/sso/////////////////////////////////////////////////////////////////////////////////////ss/
*/