소 객 알고리즘 주간 연습 - rine Loves Dynamic Graph (최 단 로 + 분 층 도)

총결산
BUG 1: 카드 상, 1s, vector 로 좀 쉬 세 요.2: 인삼 을 입 을 때 절대 치 를 취한 다.
생각의 시간 변화 에 따라 변 의 주기 가 3 f (x) = {x t = 0 1 1 − x t = 1 1 − x x t = 1 − x x x t = 2 f (x) = \ \ \ begin {cases} x & \ \ text{t = 0} \ \ \ \ \ \ \ \ \ \ \ frac {1} {1 - x} & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ frac {1 - x} {- x} {- x} & \ \ \ \ \ \ \ \ \ \ text{t {t =} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x1 − x1 − x t = 0t = 1t = 2
어떻게 하면 가장 짧 은 길 을 레이 어 링 그림 으로 달 리 는 것 이 좋 습 니 다. 아 닙 니 다. 배 울 수 있 습 니 다. 그리고 가장 짧 은 길 을 달 리 는 것 이 바로 dijkstra 템 플 릿 문제 입 니 다.
제목 링크

//#pragma GCC optimize(2)
//#pragma GCC target ("sse4")
#include
//typedef long long ll;
#define ull       unsigned long long
//#define int       long long
#define F           first
#define S           second
#define endl        "
"//<
#define eps         1e-6
#define base        131
#define lowbit(x)   (x&(-x))
#define PI          acos(-1.0)
#define inf         99999999999
#define MAXN        0x7fffffff
#define INF         0x3f3f3f3f3f3f3f3f
#define ferma(a,b)  pow(a,b-2)
#define mod(x)      (x%mod+mod)%mod
#define pb          push_back
#define decimal(x)  cout << fixed << setprecision(x);
#define all(x)      x.begin(),x.end()
#define rall(x)      x.rbegin(),x.rend()
#define memset(a,b) memset(a,b,sizeof(a));
#define IOS         ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
template<typename T> inline T fetch(){T ret;cin >> ret;return ret;}
template<typename T> inline vector<T> fetch_vec(int sz){vector<T> ret(sz);for(auto& it: ret)cin >> it;return ret;}
template<typename T> inline void makeUnique(vector<T>& v){sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());}
void file()
{
#ifdef ONLINE_JUDGE
#else
    freopen("D:/LSNU/codeforces/duipai/data.txt","r",stdin);
    //  freopen("D:/LSNU/codeforces/duipai/WA.txt","w",stdout);
#endif
}
const int N=1e5+5;
struct node
{
    int v,next;
    double w;
    bool operator<(const node& b)const
    {
        return w<b.w;
    }
}e[N*2*3*3];
int cnt=0,head[N*3];
bool vis[N*3];
void add(int from,int to,double w)
{
    e[++cnt].next=head[from];
    e[cnt].v=to;
    e[cnt].w=w;
    head[from]=cnt;
}
double dis[N*3];
signed main()
{
    IOS;
    file();
    int n,m;
    cin>>n>>m;
    while(m--)
    {
        int u,v;
        double x;
        cin>>u>>v>>x;
        add(u,n+v,x);
        add(v,n+u,x);

        x=1.0/(1.0-x);
        add(n+u,2*n+v,abs(x));
        add(n+v,2*n+u,abs(x));

        x=1.0/(1.0-x);
        add(2*n+u,v,abs(x));
        add(2*n+v,u,abs(x));
    }
    priority_queue<pair<double,int> >pri;
    for(int i=1;i<=n*3;i++)
        dis[i]=inf;
    dis[1]=0;
    pri.push({0,1});
    while(!pri.empty())
    {
        pair<double,int> u=pri.top();
        pri.pop();
        for(int i=head[u.S];i;i=e[i].next)
        {
            int v=e[i].v;
            if(dis[u.S]+e[i].w<dis[v])
            {
                dis[v]=dis[u.S]+e[i].w;
                pri.push({-dis[v],v});
            }
        }
    }
    double ans=min({dis[n],dis[n*2],dis[n*3]});
    decimal(3);
    if(ans==inf)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;




    return 0;
}