Code NK05DSRT - Sa mạc bị sai

[nam_tran6 (nam tran)]

Chào mọi người, em đang làm bài này lâu rồi mà vẫn bị WA :((
đây là link đề: https://oj.vnoi.info/problem/nk05dsrt

Bờm vô tình bị lạc vào trong 1 ốc đảo có 1 bộ tộc thổ dân sinh sống trong 1 lần đi qua sa mạc. Bờm muốn thoát khỏi sa mạc để về nhà. Người thổ dân đã cho anh một bản đồ vùng sa mạc này.

Sa mạc gồm N ốc đảo, M đường đi an toàn nối với nhau và tại mỗi ốc đảo lại có 1 hồ chứa nước rất lớn và nước chứa trong các hồ này không bao giờ cạn. Tuy nhiên hiện tại, không có nước trong các hồ.

Giả sử : Bờm đang ở ốc đảo 1, về để về đến nhà thì Bờm phải đi đến ốc đảo N. Người thổ dân cho biết rằng tại vùng sa mạc này, nếu Bờm đi đoạn đường có độ dài là L, thì Bờm phải mang uống đủ lượng nước là L, bằng không Bờm sẽ chết. Từ đó, người thổ dân đã chỉ cho Bờm cách có thể về nhà: Bờm phải vận chuyển nước từ ốc đảo 1 đển tích trữ trong các hồ tại những ốc đảo khác bằng các con đường an toàn đã có, từ đó anh có thể về nhà. Tuy nhiên, lại có 1 khó khăn khác là: trong bất cứ thời gian nào, Bờm không thể mang lượng nước quá C (do thể lực có hạn ^_^).

Yêu cầu : Hãy tìm cách giúp Bờm về nhà nhưng đồng thời sử dụng ít nước nhất (do trong sa mạc, nước rất quí!!!)

Input

Dòng đầu tiên gồm một số nguyên t cho biết số lượng test, mỗi test có dạng như sau:

• Dòng đầu tiên là 3 số nguyên N M C ngăn cách nhau bởi khoảng trắng
• M dòng tiếp theo mỗi dòng gồm 3 số nguyên I J L với y nghĩa có đường đi từ ốc đảo I đến ốc đảo J và ngược lại là an toàn và có độ dài L.

Output

Với mỗi bộ test xuất ra đúng 11 số nguyên chỉ lượng nước ít nhất cần dùng.

Giới hạn

• 1≤N, M, C≤100
• 1≤L≤30,000

Sample Input

Copy

1
9 10 25
1 2 3
2 3 12
3 4 4
3 5 9
4 9 13
5 9 5
2 6 10
6 7 10
7 8 10
8 9 10

Sample Output

Copy

65

Note

• Mang 25 nước từ 1 đến 2 sau đó lại quay về 1. Do đó, tại 2 có 19 nước. (Bờm đã uống hết (3+3) nước trong lần đi và về, (19=25−3−3)).
• Lặp lại như thế 1 lần nữa, Bờm đã mang đến 2 thêm 19 nước. Sau đó lại từ 1, Bờm mang theo 15 nước đến 2. Vậy khi đến 2, Bờm có tại đây (19+19+12=50) nước.
• Tiếp theo, Bờm lại mang 25 nước đi từ 2 đến 3, rồi quay về 2, như vậy, tại 3 có (25−12−12=1) nước. Từ 22, Bờm mang 25 nước còn lại đi đến 3. Tại 3, Bờm có được (1+(25−12)=14) nước.
• Cuối cùng, Bờm mang 14 nước đi đến 5 rồi đến 9. Vậy là Bờm đã thoát khỏi sa mạc.

ý tưởng của em là sử dụng thuật toán dijkstra từ n để đến 1, có một hàm để tính
em không hiểu ý tưởng hay là code của em bị lỗi chỗ nào mà lại bị Wrong answer, mong anh chị nào xem giúp em với ạ
đây là code của em: https://ideone.com/Vaz5Xi

#include <bits/stdc++.h>

using namespace std;
long long q,m,n=0,c,u,v,w,price[222];
vector<pair<int,long long> >l[222];
struct cmp{
    bool operator()(pair<int,long long>x,pair<int,long long>y)
    {
        return x.second>y.second;
    }
};
priority_queue<pair<int,long long>,vector<pair<int,long long> >,cmp>s;
pair<int,long long>tam,temp;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>q;
    while(q--)
    {
        for(int i=1; i<222; i++)
            l[i].clear();
        cin>>n>>m>>c;
        for(int i=1; i<=n; i++)
            price[i]=1e18;
        for(int i=1; i<=m; i++)
        {
            cin>>u>>v>>w;
            l[u].push_back({v,w});
            l[v].push_back({u,w});
        }
        price[n]=0;
        s.push({n,0});
        while(!s.empty())
        {
            tam=s.top();
            s.pop();
            if(tam.second!=price[tam.first])continue;
            u=tam.first;
            for(int i=0; i<l[u].size(); i++)
            {
                temp=l[u][i];
                long long need=tam.second,ca=temp.second;
                if(need+ca<=c)temp.second=need+ca;
                else
                {
                    if(c<=2*ca)continue;
                    long long t=(need+ca-c)/(c-2*ca);
                    if((need+c-ca)%(c-2*ca)!=0)t++;
                    temp.second=(2*t+1)*ca+need;
                }
                if(price[temp.first]>temp.second)
                {
                    price[temp.first]=temp.second;
                    s.push(temp);
                }
            }
        }
        cout<<price[1]<<'\n';
    }
    return 0;
}

nếu được thì có anh/chị nào có thể check giúp code em chưa được ở chỗ nào không ạ?, vì em có đọc qua sol, thấy đúng ý tưởng mà code kiểu gì cũng bị sai kết quả.
em xin cảm ơn trước.

[SITUVN.gcd]

Bạn vui lòng đưa trực tiếp bài làm của bạn lên đây, bọn mình không truy xuất được nội dung trên VNOI vì yêu cầu phải có tài khoản.

[nam_tran6 (nam tran)]

em đã đổi link sang ideone rồi ạ