首页 > 代码库 > [题解]UVA10986 Sending email

[题解]UVA10986 Sending email

2024-07-10 20:56:17   215人阅读

链接：http://vjudge.net/problem/viewProblem.action?id=24941

描述：n个点，m条边的无向图，寻找从S到T的最短路。

思路：基础的单源点最短路 用Dijkstra或spfa都可以解决

 

这是我的实现：

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <queue>  5 using namespace std;  6 #define MaxN 20020  7 #define MaxM 100020  8 struct node  9 { 10     int v,dist; 11     node *next; 12 }; 13 node Edge[MaxM]; 14 node *cnt=&Edge[0]; 15 node *adj[MaxN]; 16 int dist[MaxN]; 17 int N,INF; 18 int n,m,S,T; 19 inline void Get_int(int &Ret) 20 { 21     char ch; 22     bool flag=false; 23     for(;ch=getchar(),ch<‘0‘||ch>‘9‘;) 24         if(ch==‘-‘) 25             flag=true; 26     for(Ret=ch-‘0‘;ch=getchar(),ch>=‘0‘&&ch<=‘9‘;Ret=Ret*10+ch-‘0‘); 27     flag&&(Ret=-Ret); 28 } 29 inline void Clean() 30 { 31     memset(Edge,0,sizeof(Edge)); 32     cnt=&Edge[0]; 33     memset(adj,0,sizeof(adj)); 34 } 35 inline void Addedge(int u,int v,int w) 36 { 37     node *p=++cnt; 38     p->v=v; 39     p->dist=w; 40     p->next=adj[u]; 41     adj[u]=p; 42  43     p=++cnt; 44     p->v=u; 45     p->dist=w; 46     p->next=adj[v]; 47     adj[v]=p; 48 } 49 inline void Read_Build() 50 { 51     Get_int(n);Get_int(m);Get_int(S);Get_int(T); 52     int i,u,v,w; 53     for(i=1;i<=m;++i) 54     { 55         Get_int(u);Get_int(v);Get_int(w); 56         Addedge(u,v,w); 57     } 58 } 59 struct cmp 60 { 61     bool operator()(node a,node b) 62     { 63         return a.dist>b.dist; 64     } 65 }; 66 priority_queue <node, vector<node>, cmp> q; 67 void Dijkstra(int s) 68 { 69     node c,d; 70     node *p; 71     int i,j,k; 72     memset(dist,0x3f,sizeof(dist)); 73     INF=dist[s]; 74     dist[s]=0; 75     c.v=s;c.dist=0; 76     q.push(c); 77     while(!q.empty()) 78     { 79         d=q.top();q.pop(); 80         j=d.v; 81         for(p=adj[j];p!=NULL;p=p->next) 82         { 83             k=p->v; 84             if(dist[k]>dist[j]+p->dist) 85             { 86                 dist[k]=dist[j]+p->dist; 87                 d.v=k;d.dist=dist[k]; 88                 q.push(d); 89             } 90         } 91     } 92 } 93 inline void Print() 94 { 95     if(dist[T]==INF) 96         printf("unreachable\n"); 97     else 98         printf("%d\n",dist[T]); 99 }100 int main()101 {102     Get_int(N);103     for(int i=1;i<=N;i++)104     {105         printf("Case #%d: ",i);106         Clean();107         Read_Build();108         Dijkstra(S);109         Print();110     }111     return 0;112 }
View Code

 


联系
我们