【G - MPI Maelstrom】

    xiaoxiao2022-07-13  152

    思路:

    翻译题…翻译题…难道是我校被Q了吗?正权无向稠密图,求源点到所有点的最短路,输出最长一条的长度。使用:Dijkstra,邻接矩阵,atoi函数。

    代码:

    0ms 748kB ​//0ms 748kB #include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cstring> #define INF 0x3f3f3f3f using namespace std; const int maxn = 105; int N; int mp[maxn][maxn]; int dis[maxn]; struct NODE{ int id; int dis; friend bool operator > (NODE a , NODE b){ return a.dis > b.dis; } NODE(int id,int dis) : id(id) , dis(dis) {} ; }; priority_queue<NODE , vector<NODE> , greater<NODE> > Q; bool vis[maxn]; int ans = 0; void IJK(){ memset(vis,0,sizeof(vis)); memset(dis,INF,sizeof(dis)); Q.push(NODE(1,0));dis[1]=0; while(Q.size()){ NODE cur = Q.top() ; Q.pop() ; if(vis[cur.id]) continue; vis[cur.id] = true; for(int i=1;i<=N;i++){ if(vis[i]) continue; if(dis[i] > dis[cur.id] + mp[cur.id][i]){ dis[i] = dis[cur.id] + mp[cur.id][i]; Q.push(NODE(i,dis[i])); } } } for(int i=1;i<=N;i++) if(dis[i] == INF) continue; else ans = max(ans , dis[i]); return ; } int main(){ cin>>N; for(int i=2;i<=N;i++){ for(int j=1;j<=i-1;j++){ char str[30]; scanf("%s",str); if(str[0] == 'x') mp[i][j] = mp[j][i] = INF; else mp[i][j] = mp[j][i] = atoi(str); } } for(int i=1;i<=N;i++) mp[i][i] = 0; IJK(); cout<<ans<<endl; return 0; }
    最新回复(0)