P1286 最短路径 部分样例未通过,不知道为什么
- #include <bits/stdc++.h>
- using namespace std;
- int n,m;
- struct edge
- {
- int u;
- int v;
- int w;
- };
- vector<edge>edges;
- vector<int>G[100];
- int dis[100];
- int vis[100];
- void init()
- {
- for(int i=0;i<n;i++)
- {
- G[i].clear();
- }
- edges.clear();
- memset(dis,0x3f3f3f3f,sizeof(dis));
- memset(vis,0,sizeof(vis));
- }
- void adde(int u,int v,int w)
- {
- edges.push_back(edge{u,v,w});
- int sz=edges.size()-1;
- G[u].push_back(sz);
- }
- int getlong(int k)
- {
- int ans=1;
- while(k--)
- {
- ans=ans*2%100000;
- }
- return ans;
- }
- void spfa(int s)
- {
- dis[s]=0;
- vis[s]=1;
- queue<int>q;
- q.push(s);
- while(!q.empty())
- {
- int u=q.front();q.pop();
- vis[u]=0;
- for(unsigned int i=0;i<G[u].size();i++)
- {
- edge e =edges[G[u][i]];
- if(dis[e.v]>dis[u]+e.w)
- {
- dis[e.v]=dis[u]+e.w;
- if(!vis[e.v])
- {
- vis[e.v]=1;
- q.push(e.v);
- }
- }
- }
- }
- }
- int main() {
- while(cin>>n>>m)
- {
- init();
- for(int...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
主要问题在于错误地提前对边权进行了取模运算，导致在比较路径总长度时使用了错误的值。正确的方法应避免在计算路径时取模，而是在最终结果输出时处理。然而，由于边权过大，无法直接计算，需采用并查集结合贪心策略，按边的顺序处理，确保路径的最优性。